珂朵莉树
老司机树，ODT(Old Driver Tree)，又名珂朵莉树（Chtholly Tree)。起源自 CF896C。
前置知识
会用 STL 的 set。
一些常用的函数：
s.upper_bound(x) ，s.insert().first （返回插入后的迭代器）
s.erase(iterator_begin, iterator_end) 删掉 $[begin, end)$ 的值。
核心思想
把值相同的区间合并成一个结点保存在 set 里面。
因此 ODT 一般都用于有区间赋值的操作。
复杂度
在数据随机的情况下，对于如 add assign sum 函数，总的时间复杂度为 $O(n \log \log n)$，注意不是单次
但是数据特地卡的话，可以卡成 $O(n^2 \log n)$
主要内容
节点信息
l r表示区间左右端点v表示节点的信息，注意是整个区间共同的信息。
struct odt_node {
int l, r;
mutable int v;
odt_node (const int &_l, const int &_r, const int &_v) : l(_l), r(_r), v(_v) {}
inline bool operator<(const odt_node &o) const {
return l < o.l;
}
};
split
珂朵莉树的核心操作：将一个包含 $x$ 的区间 $[l, r]$ 分裂成 $[l, x - 1], [x, r]$。
并且返回包含 $x$ 的区间。
auto split (int x) {
if (x > n) return odt.end();
auto it = --odt.upper_bound({x, 0, 0});
if (it->l == x) return it;
// auto [l, r, v] = *it;
int l = it->l, r = it->r, v = it->v;
odt.erase(it);
odt.insert({l, x - 1, v});
return odt.insert({x, r, v}).fi;
}
通过这个函数可以将某个区间的操作转换成 $[split(l), split(r + 1))$。
具体来说是先分裂，然后得到对应 $l$ 的区间，以及 $r + 1$ 的区间。
auto itr = split(r + 1), itl = split(l);
一定要先右，再左，否则会RE
然后迭代区间，进行操作即可。
for (; itl != itr; itl++) {
auto [l, r, v] = *itl;
// do sth
}
复杂度非常的玄学，但是有 资料 证明出了复杂度再随机的情况下不会非常的高。
assign
注意左右迭代器一定一定是 先右端点，再左端点，否则会 RE
该函数是将 $[l, r]$ 之间的若干个区间删掉，然后替换成一个完整的 $[l, r]$
void assign (int l, int r, int v) {
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert({l, r, v});
}
sum
求区间 $[l, r]$ 的信息。
int sum (int l, int r) {
int res = 0;
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; itl++) {
auto [l, r, v] = *itl;
// res += v ? (r - l + 1) : 0;
}
return res;
}
flip
区间取反。
void flip (int l, int r) {
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; itl++) {
itl->v ^= 1;
}
}
初始化以及一些细节
以上是常用的函数。
在初始化的时候，比方说需要 $[1, n]$ 区间的信息，最后一定要添加一个 $[n + 1, n + 1]$ 的空区间，使得不会发生越界。
for (int i = 0; i < n; i++) {
int x;
cin >> x;
odt.insert({i, i, x});
}
odt.insert({n, n, INF});
