[珂学の暴力]ODT / Chtholly Tree

0x00 Prologue

最近闲下来了...刷CF的时候奇奇怪怪地刷到了珂朵莉round(Codeforces Round #449 (Div. 1))。里面的题可以说是非(shí)常(fēn)奈(dú)斯(liú)了。其中有一道题很有趣——CF896C(洛谷)。写一个数据结构，支持以下4个操作

将区间中的所有数加上
将区间中的所有数改成（这个是ODT优势体现的操作）
输出区间中第大的数
输出 $sum_{i=L}^{R}a_i^k$ ，即区间内元素的次幂和

数据随机！

对于这类有区间推平操作数据又随机的题，ODT就十分适用了

UPD @ 04 / 29 / 18 04:33 p.m.

（julao @Guanghao Ye来批判了：老司机树原版是lxl搞的！老司机树原版是lxl搞的！老司机树原版是lxl搞的！）。

~~老司机擅长推车，珂朵莉擅长推平区间！~~

本文将以这道题作为例子讲解Old Driver Tree / 珂朵莉树的智慧 / 暴力美学。

0x01 如何维护？

珂朵莉树将区间信息以三元组的形式存储，即用表示中的元素为。从这里就能看出为什么珂朵莉树对于区间推平较为高效了。我们用set存储这些三元组，内部维护这些区间，以左端点作为关键字进行升序排列，这样方便我们进行一些操作的时候方便查找到我们想要修改的区间。区间节点结构如下：

struct Node { int l, r; mutable ll v; // 在用迭代器访问时能够修改值 Node(){} Node(int L, int R=-1, LL V=0l): l(L), r(R), v(V){} bool operator < (const Node& b) const { return l < b.l; }};

一些操作？不不不，其实核心操作只有一个：split(p)——将所在区间拆分为和。

由于在set中的所有节点是有序的，我们可以用lower_bound(x)定位我们要操作的区间。（注: lower_bound(x)可以在$logn$时间内在一个有序序列中找到最小的使得并返回的位置 / 迭代器，一个二分查找的过程）

这时我们要分以下两种情况处理通过找到的区间：

如果已经是某个区间的左端点，那么我们直接返回查找到的迭代器;
如果不是某个区间的左端点，那么当前返回的迭代器所指向的区间是所在区间右边第一个区间。这时将迭代器后移一位。如果在后移之后，比当前区间的右端点还大，那么直接返回尾迭代器(因为不需要进行操作)；否则，那么记录一下当前区间的信息，然后直接删除当前区间再插入拆分好的区间和，最后返回所在区间的迭代器(操作只会影响包含的区间)。

inline set<Node>::iterator split(int p) { auto it = s.lower_bound(Node(p)); if(it != s.end() && it->l == p) return it; // 情况一 --it; // 找到p所在区间 if(it->r < p) return s.end(); // 不需要拆分 int L = it->l, R=it->r; // 记录信息 LL v = it->v; s.erase(it); s.insert(Node(L, p - 1, v)); // 插入新区间 return s.insert(Node(p, R, v)).first;}

0x02 实现操作

1. 区间赋值

有了split之后，我们就能利用split做各种神(bao)奇(li)的操作了。先来看一个区间赋值的操作。

现在给定了我们 , 和。首先为了能够暴力，我们先把和所在区间各自拆分出来。既然我们是区间赋值(推平)，我们可以直接将从set中移除再添加一个新的区间，其中的值为 :

inline void modify(int l,int r,int v) { auto R=split(r+1), L = split(l); s.erase(L, R); s.insert(Node(l, r, v)); return;}

在这个操作的过程中会有许多小区间被合并到，因此空间复杂度会大大减小。

2. 区间加

第一步与区间赋值一样，首先拆分和。之后，我们直接暴力修改中的值，由于数据随机，所以复杂度并不会爆时间。

inline void add(int l, int r, int v) { auto R = split(r+1), L=split(l); while(L != R) { L->v += v; ++L; } return;}

区间$k$次幂和与区间加操作十分类似，大家可以尝试写一个。

3. 区间第 大

这才是真正的暴力。第一步依旧是拆分与。然后我们将中所有区间拿出来，将区间长度和区间值存到pair，放到vector里，然后对其中所有区间按照升序排列。然后遍历vector，每次将减去当前区间长度，直到。十分的暴力，但是由于数据随机和区间合并时导致区间数量减少，我们依旧能过题。

inline ll kth(int l, int r,int k) { auto R = split(r+1), L = split(l); vector<pii> vec; while(L != R) { vec.push_back(make_pair(L->v, L->r - L->l + 1)); ++L; } sort(vec.begin(), vec.end(), [=](pii a, pii b) -> bool { return a.first < b.first; }); for(auto i: vec) { k -= i.second; if(k <= 0) return i.first; } return -1;}