珂朵莉树
珂朵莉树（Chtholly Tree），又名老司机树 ODT（Old Driver Tree）。起源自 CF896C。
实际上，这种想法的本质是基于数据随机的「颜色段均摊」，而不是一种数据结构。
使用 set 实现的珂朵莉树的 assign、add、sum 操作复杂度为 $O(n\log\log n)$.
ODT 的核心思想是将值相同的区间合并为一个结点维护，只要有区间赋值的题目都可以用 ODT 骗分。
ODT 在随机数据上表现良好，但是不保证数据随机时，会被构造数据卡到 T 飞。
内容基本来自 OI-Wiki。
struct Note_t {
int l, r;
mutable int v;
Node_t(const int &il, const int &ir, const int &iv)
: l(il), r(ir), v(iv) {}
bool operator<(const Node_t &o) const { return l < o.l; }
}
其中，v 是附加数据。
Note
mutable用于突破const的限制，即使Note_t被设为常量，仍能改变v的值。这意味着，我们可以直接修改已经插入
set的元素的v值，而不用将该元素取出后重新加入set。
接下来，我们定义一个 set 存储节点。
set<Node_t> odt;
typedef set<Node_t>::iterator iter;
iter 用于简化代码，如果题目支持 C++11，也可以使用 auto。
split 是核心操作之一，用于将包含 $x$ 的区间 $[l,r]$ 分裂为 $[l,x)$ 和 $[x,r]$，并返回后者的迭代器。
iter split(int x) {
if (x > n) return odt.end();
auto it = --odt.upper_bound(Node_t(x, 0, 0));
if (it->l == x) return it;
int l = it->l, r = it->r, v = it->v;
odt.erase(it);
odt.insert(Node_t{l, x - 1, v});
return odt.insert(Node_t(x, r, v).first;
}
assign 是另一个核心操作，用于对区间赋值，可以降低节点数量，保证了 ODT 的时间复杂度。
void assign(int l, int r, int v) {
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert(Node_t(l, r, v));
}
ImportantODT 必须先
split右端点，再split左端点，这和迭代器的失效有关。不这样做，代码会随机 $\textcolor{purple}{\text{RE}}$。
参考代码如下：
void assign(int l, int r, int v) {
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; ++itl) {
// Perform Operations here
}
}