珂朵莉最可爱了。
好了不废话了，直接开始珂朵莉树。
什么是珂朵莉树
珂朵莉树，又叫老司机树，英文名字 \(\text{ODT}\)，是一种支持区间平推的乱搞数据结构，在数据随机时表现十分优秀。
操作
定义
珂朵莉树有链表和集合（\(\text{set}\)） 两种定义方法，一般来说，使用 \(\text{set}\) 定义的比较普遍。
珂朵莉树的思想主要是将所有颜色相同（也就是数值相同）的区间缩成一个一个的块，将这些块的左右端点插入 \(\text{set}\) ，再进行后续操作。
举个小栗子，比如我现在有数列 \(a = \{ 1, 1, 2, 2, 1, 1, 1, 3\}\)，那么珂朵莉树里就应该存的是这样的信息：
\(s = \{\{1, 2, 1\}, \{3, 4, 2\}, \{5, 7, 1\}, \{8, 8, 3\}\}\)
解释一下第一个块表示的信息：左端点是 \(1\)， 右端点是 \(2\)（即在区间 \([1, 2]\) 中），里面的数都是 \(1\)。
据证明，珂朵莉树在两个条件以下两个条件下复杂度优秀：
- 数据随机
- 操作中有平推操作
如果满足上面两个条件，珂朵莉树的复杂度就可以做到优秀的 \(O(n \log \log n) -O(n\log n)\) 了。
这样，我们就只需要在 \(\text{set}\) 中放入每个块的左右端点以及权值，并且按照左端点排序即可。
struct node {
int l, r;
mutable int v; // 注意这里的 mutable 一定不能改
node(int L, int R = -1, int V = 0):l(L), r(R), v(V){}
bool operator < (const node& W)const { // 按左端点排序
return l < W.l;
}
};
set<node> s;
#define itset set<node> :: iterator // 宏定义迭代器
建树
建树没啥好说的，就是把初始所有的点一个一个插进去。
for (int i = 1; i <= n; i ++ )
s.insert(node(i, i, w[i]));
分裂（split）
\(\text{split(pos)}\) 操作是将 \(\text{pos}\) 所在的块分成两个，并返回右边块所在的迭代器。
当然，我们只需要在 \(\text{set}\) 中找到 \(\text{pos}\) 所在的迭代器，找到这个块的左端点 \(l\) 和右端点 \(r\)，删除原块，并加入 \([l, pos), [pos, r]\) 两块即可。
itset split(int pos) {
itset p = s.lower_bound(node(pos)); // 找到左端点大于等于 pos 的第一个块
// 当然也就是找到 pos 所在块右边的第一个块
if (p != s.end() && p -> l == pos) return p;
-- p; // pos 所在块就是 p
int ls = p -> l, rs = p -> r, vv = p -> v;
s.erase(p);
s.insert(node(ls, pos - 1, vv));
return s.insert(node(pos, rs, vv)).first;
}
平推（assign）
\(\text{assign(l, r, v)}\) 操作是将 \([l, r]\) 区间内都替换成 \(v\)。
当然，我们只要将 \(l, r\) 分裂出来，将 \([l, r + 1)\) 之间的删掉，最后插入块 \((l, r, v)\) 即可。
void assign(int l, int r, int v) {
itset rs = split(r + 1), ls = split(l); // 注意这里 l, r 也不能反，r 别忘了加一（因为右端是开区间）
s.erase(ls, rs);
s.insert(node(l, r, v));
}
其他操作
操作思路和平推基本一样，就是取出 \([l, r]\) 之间的所有块，然后再一个一个处理即可。专家已经证明了，数据随机且平推的情况下，块数均摊不超过 \(\log n\)，所以就可以这样暴力乱搞了。
比如求 \([l, r]\) 之间的所有数的和：
int query(int l, int r) {
itset rs = split(r + 1), ls = split(l);
int ans = 0;
for (itset it = ls; it != rs; it ++ )
ans += (it -> r - it -> l + 1) * it -> v;
return ans;
}
好了，现在你已经完全掌握珂朵莉树了，拿几道小题练练手吧！
例题
CF915E Physical Education Lessons
CF896C Willem, Chtholly and Seniorious （这个是模板题，但是并不好）
这些题后面可能还会补上题解。先挖个坑
原文地址：http://www.cnblogs.com/LcyRegister/p/16908422.html
