乱讲珂朵莉树
结合 OI.wiki 和我的经验乱改的。
应该没有瑕疵了，有的记得私信或喷我。
乱改 by @aaron0919
免责声明
不好意思，例题全是某臭名昭著上的。但 UOJ 的幻灯片还是太高级了就放这了。
本幻灯片无商业用途，仅供学习交流。
其实是写来给xxs看的。
写的不好可以喷，随便点差评，反正是写来给xxs看的。
！！竟然花了我 $5$ 个小时！！
什么是 ODT
珂朵莉树，颜色段均摊，由 数据删除 的 CF896C 而得名。
其核心思想是利用推平操作，将一个区间变为左端点，右端点，值三个量，用 set 或链表将其按左端点排序，从而将每段区间串联起来。
这种数据结构极为暴力，它其实并不是一棵树，只是一个序列，但传统 ODT 在随机数据下可以达到均摊 $O(n\log n)$ 的优秀复杂度，跳表/set版本可以更快 $O(n\log\log n)$。以下介绍的 ODT，均为使用 set 实现的 ODT。
ODT 的原理
将值相同的一段区间合并成一个结点处理。相较于传统的线段树等数据结构，对于含有区间覆盖的操作的问题，珂朵莉树可以更加方便地维护每个被覆盖区间的值。
ODT 的复杂度
如果要保证复杂度正确，必须保证数据随机。详见 Codeforces 上关于珂朵莉树的复杂度的证明。更详细的严格证明见 珂朵莉树的复杂度分析。证明的结论是：用 std::set 实现的珂朵莉树的复杂度为 $O(n \log \log n)$，而用链表实现的复杂度为 $O(n \log n)$。
ODT 的操作
ODT 有两个基本操作，分裂和推平，即 spilt 和 assign。
对于分裂操作，在 set 内二分目标点所在块，删除该块，插入从目标点分裂开的两个块，复杂度为 $O(\log n)$。
对于推平操作，先将目标区间的两端分割下来，删除目标区间内所有块，插入一个由左端点，右端点，目标值组成的新块，复杂度与分裂相同。
推平操作主要保证低复杂度，分裂操作用于获取区间。
基于这两个操作，我们可以完成区间加，区间最值等许多操作。
ODT 的简单实现
(我的垃圾马蜂,不是大佬${\color{red}W}ind\_love$的)
节点
种锁粥汁，mutable 是 const 的反义词。
旧似嗦，我们可以直接修改已经插入 set 的元素的 val 值，而不用将该元素取出后重新加入 set。
struct nde
{
int l, r;
mutable int val;
bool operator<(const nde &other) const { return l < other.l; }
};初始化
初始化时，向珂朵莉树中插入一个极长区间（如题目要求维护位置 $1$ 到 $n$ 的信息，插入区间 $[1,n+1]$）。
set<nde> s;
int main()
{
cin >> n;
s.insert({1, n + 1, 0});
}分裂
将 $[l,r]$ 裂成 $[l,x),[x,r]$ 并返回后者。
auto split(int x)
{
auto p = s.lower_bound({x, 0, 0});
if (p != s.end() && p->l == x)
{
return p;
}
--p;
auto [l, r, val] = *p;
s.erase(p);
s.insert({l, x - 1, val});
return s.insert({x, r, val}).first;
}推平
有了 split，剩下的乱打就行了。
因为有 split(r + 1) 这种东西，自然初始区间就要设为 $[1,n+1]$。
void assign(int l, int r, int x)
{
auto q = split(r + 1), p = split(l);
s.erase(p, q);
s.insert({l, r, x});
}例子-区间求和
真的就是乱打，但注意先 split 右端点再 split 左端点。
int sum(int l, int r)
{
int res = 0;
auto q = split(r + 1), p = split(l);
for (auto it = p; it != q; ++it)
{
(res += it->val * (it->r - it->l + 1)) %= MOD;
}
return res;
}ODT可解决的问题
一般来讲，珂朵莉树可解的问题要求必须有推平操作，且数据尽可能随机，否则可以被卡成平方。
从 CF896C 这道老祖宗例题来讲，要求维护一个序列，支持区间加，区间推平，区间第 $k$ 小，区间次幂和。
传统意义上讲，这类题目应该用线段树解决，但线段树不便维护区间次幂和，且码量较大，${\color{red}W}ind\_love$看到这题的唯一线段树做法暴力求了区间次幂和。
但是如果使用珂朵莉树，只需要维护上述三个基本值，再配合上简单的暴力，就可以解决本题。
ODT的相关运用
拎了一大堆我也不会的例题，凑合着讲讲吧。
ODT与其他数据结构
例题 P8512。
和其他多数据结构结合的题目类似，这里主要是利用了 ODT 便于推平的特性。
说白了，维护每个时间戳染的颜色对答案的贡献，如果覆盖了之前覆盖过的区间，则需要减去之前的贡献。
就可以离线下来，通过前缀和求出答案。
这样的题目有一个共性，就是每次操作的答案间必须有联系，而这种联系必须可以被其他数据结构或算法所维护，这类题目的关键就是找到并维护这种联系。
ODT与树链剖分
众所周知，一道数据结构题只要上树就变成了一道新题。
例题 P2146。
这题只需要维护区间推平与全局求和。
注意到卸载和安装的方向，一个需要推平整个子树，另一个则是推平从当前点到根的路径。
含有推平操作，则使用 ODT 更为简便，重链剖分后直接推平即可。
ODT 与区间翻转
这例题是我找的，我的垃圾提交记录，RE/MLE 了 $37$ 发。
这题需要求和推平区间加，还有区间的翻转交换和复制。
因为 ODT 使用 set，对区间进行了动态排序，所以很适合处理区间翻转的问题。
在处理翻转操作时，只需要算出该区间左右边界在翻转后的位置，直接修改即可，记得交换左右边界。
ODT 与区间复制和交换
很自然的还是上题。
然后再说一下如何实现区间复制和交换，复制比较简单，把原区间所有段拿出，删除目标区间内段，改变左右边界后将原区间内块插入即可。
区间交换稍微复杂一点，需要将两个区间取出，在 ODT 中删除，再改变两区间内块的左右边界，最后插入即可。
ODT思想的推广
ODT思想，即靠左右边界及一个或多个数值表示一个区间的思想。
一般情况下，我们保存这个区间内数的值，但有时，这个数值还可以表示其他内容。
垃圾例题
例题是 P11833，联合省选 D2T1，推箱子。
按时间排序的贪心是容易想到的，这里讲后面的操作部分。
我们注意到，把一排箱子一起推动后，其位置形成一个公差为 $1$ 的等差数列。
则我们保存区间的首项，就可以表示出这个区间内的所有数。
然后需要写比较复杂的模拟，求出每个箱子推完后的时间，判断是否满足限制即可。
很可惜，Wind_love 还有我在考场上都没有写出来。
所以太伤心了代码被我吃了。
高级进阶
总结
ODT 代码简单，思维暴力，适于维护易被表示的区间，但要求直接或间接有区间推平操作。
同时，它可以简单的维护几乎所有线段树可维护的内容，在适当情况下可以代替其他数据结构使用。
极其简单的例题
彩蛋
在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的人们，人人本着正义之名。长存不灭的过去、逐渐消逝的未来，我回来了。纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。
----世上最幸福的女孩：珂朵莉
好题分享
