## 什么是珂朵莉树？
**珂朵莉树**，别名颜色段均摊、ODT，它是 $2017$ 年一场 CF 比赛中提出的数据结构，因为题目背景主角是《末日时在做什么？有没有空？可以来拯救吗？》的主角珂朵莉，因此该数据结构被称为珂朵莉树。但是珂朵莉树并不是树形数据结构，而是**线性数据结构**。
珂朵莉树的本质是**合并相邻的相同颜色**，以达到节省时间的效果。而珂朵莉树的修改与询问都是**暴力**，这使得珂朵莉树几乎无法处理区间赋值之外的区间修改或查询，但是也让珂朵莉树有非常广泛的用途。
## 常见的珂朵莉树写法
珂朵莉树通常将区间转化为值，并使用 `std::set` 来维护每个区间，同一个区间里的值是相同的。代码如下：
```cpp
struct node {
int l, r;
mutable int v;
node(int L, int R = -1, int V = 0): l(L), r(R), v(V) {}
bool operator < (const node& o) const {
return l < o.l;
}
};
typedef set<node>::iterator IT;
set<node> s;
```
代码中的 `node` 是维护了一个 $[l,r]$ 的区间，这个区间里的数值全为 $v$。
珂朵莉树有两个基本操作：
- split 裂块
```cpp
IT split (int pos) {
IT it = s.lower_bound(node(pos));
if(it != s.end() && it->l == pos) return it;
it --;
int L = it->l, R = it->r;
int V = it->v;
s.erase(it), s.insert(node(L, pos - 1, V));
return s.insert(node(pos, R, V)).first;
}
```
- `split` 的作用是将 $pos$ 所在的块 $[l,r]$ 分裂为 $[l,pos-1],[pos,r]$ 两块，时间复杂度 $\mathcal{O}(\log s)$，$s$ 是当前 `std::set` 内区间的个数。
- assign 区间赋值
```cpp
void assign(int l, int r, int val = 0) {
IT itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, val));
}
```
- 随着 `split`，珂朵莉树中的区间个数会越来越多，导致复杂度爆炸，我们需要区间赋值操作来减少区间个数。设原先区间是 $[l_1,r_1],[l_2,r_2],\cdots,[l_s,r_s]$，且 $l_1\leq l\leq r_1,l_s\leq r\leq r_s$，代码中 `assign` 操作先是通过 `split` 将区间变成 $[l_1,l-1],[l,r_1],[l_2,r_2],\cdots,[l_s,r],[r+1,r_s]$；然后通过 `std::set::erase`，删除了 $[l,r]$ 之间的所有区间，将区间变成 $[l_1,l-1],[r+1,r_s]$；最后插入区间 $[l,r]$，将区间变成了 $[l_1,l-1],[l,r],[r+1,r_s]$，完成了区间赋值。时间复杂度 $\mathcal{O}(s'\log s)$，$s'$ 是删除的区间个数。
初始化只需插入 $[1,1],[2,2],\cdots,[n,n]$ 即可。
珂朵莉树到这里，貌似非常无用，因为珂朵莉树复杂度是基于均摊的：
- 设一共进行了 $q$ 次 `assign` 操作，则时间复杂度为 $\mathcal{O}(\sum s'\log s)$。
- 已知 `std::set` 中初始有 $n$ 个区间，$q$ 次 `assign` 插入了 $q$ 的区间，所以珂朵莉树的区间总个数为 $n+q$ 个。所以珂朵莉树最多删除 $n+q$ 个区间，也就是 $\sum s'\leq n+q$。
- 由于 `std::set` 最多同时有 $n$ 个区间，珂朵莉树最多删除 $n+q$ 个区间，所以 $q$ 次 `assign` 的时间复杂度总和为 $\mathcal{O}((n+q)\log n)$，均摊一次 $\mathcal{O}(\log n)$。
- 同时，如果珂朵莉树的区间询问与区间赋值绑定，则区间询问的时间复杂度也是 $\mathcal{O}(s'\log s)$，均摊 $\mathcal{O}(\log n)$。
基于均摊，珂朵莉树可以以非常优秀的复杂度完成暴力才能维护的操作。这使得它有非常多的应用：
1. LOJ #6284. 数列分块入门 8
> 区间询问等于一个数 $c$ 的元素，并将这个区间的所有元素改为 $c$。
- 区间询问与区间修改绑定，可以使用珂朵莉树暴力处理询问。
时间复杂度 $\mathcal{O}((n+q)\log n)$。
1. 没有找到这个题 qwq
> 区间赋值、区间查询 $K$ 小值。
- P3332 + 珂朵莉树即可。
时间复杂度 $\mathcal{O}((n+q)\log^2 n)$。
1. 洛谷 P4690 [Ynoi2016] 镜中的昆虫
> 区间赋值、区间查询不同的数个数。
- 如果是单点修改，可以维护每个数的前驱（即上一个等于它的数，没有则为 $0$），问题就变成了区间数小于某数的数的个数。观察发现，区间修改对于颜色相同的区间只有左端点与这个颜色的后驱和原来颜色的后驱发生改变，于是使用珂朵莉树维护区间，问题变成了单点修改。
时间复杂度 $\mathcal{O}((n+q)\log n)$。
（您观察发现上文的题都是高难度评分题，但是作者其实很菜，一题都没有 A）
珂朵莉树其实有一个有趣的特性：
在随机数据下，珂朵莉树内的区间个数是 $\mathcal{O}(\log n)$ 级别的。利用这一特性，珂朵莉树在不与区间赋值绑定的情况下，也可以进行区间赋值。
但是，这只适用于数据随机的情况下，它的时间复杂度是**错误的**。由于珂朵莉树的始祖题 CF986C 利用了这一特性，所以很多人只知道珂朵莉树在数据随机下有用，就以偏概全，认为珂朵莉树的复杂度是错误的。事实上，在基于均摊的条件下，珂朵莉树有着非常优秀的复杂度。
1. CF896C Willem, Chtholly and Seniorious
> 区间加、区间赋值、区间查询 $K$ 小值、区间查询 $k$ 次方和。**数据随机**。
- ~~一看就不可做，弃了！~~ 利用数据随机的性质，我们可以使用珂朵莉树暴力处理区间修改与询问
时间复杂度 $\mathcal{O}(q\log n\log k\log\log n)$，$\mathcal{O}(\log k)$ 是查询 $k$ 次方和的快速幂的时间复杂度。
1. 洛谷 P5251 [LnOI2019]第二代图灵机
> 维护 $a,b$ 两序列。支持 $b$ 单点修改，$a$ 区间修改，查询包含 $a$ 所有颜色、$b$ 区间和最小的区间，查询没有包含 $a$ 中重复颜色、$b$ 区间和最大的区间。**数据随机**。
- 利用数据随机的性质，我们可以使用珂朵莉树维护 $a$，树状数组维护 $b$ 的区间和，线段树维护 $b$ 的区间极值。查询可以使用珂朵莉树上双指针解决。
时间复杂度 $\mathcal{O}(q\log^2n\log\log n)$，树状数组和线段树自带一只 $\mathcal{O}(\log n)$。
## 珂朵莉树的拓展
珂朵莉树与其说是一种数据结构，更想是一种思想：一种将区间化为值、维护整个区间的思想。它可以有更多的拓展：搭配分块、搭配根号重构、搭配线段树等等。它也可以基于更多数据结构：如果你搭配根号重构，你可以用平凡的数组维护……
不过到这份上，已经没有人将其叫做“珂朵莉树”了。因为它不再与相同颜色有关系，不再是 $2017$ 年一场 CF 比赛中提出的数据结构了，而是一种普遍的思想。