关于它很珂学的名字…
珂朵莉树（Chtholly Tree），又称老司机树（Old Driver Tree），起源于CodeFoeces平台上编号为896C的一道题—— “ Willem, Chtholly and Seniorious ”
（珂学家们此时不用翻译也知道这个名字是在说啥了）
，一位用户Old Driver在给出了线段树的正解之后，又发布了
YY多年的
一份前所未有的玄学解法，其中利用到的数据结构就是今日我们
喜闻乐见的
珂朵莉树。
它可以干什么
很简单，在具有
区间赋值
操作，
区间统计
操作，以及最好保证
数据随机
的情况下在
时空复杂度
上把线段树
吊起来打
（详情见后）。
也可以
在走投无路时
骗分。
你需要有哪些前置知识…
- 五分钟就能学会的C++STL中set的部分内容
- 暴力枚举
- 数学知识（如果你想证明它的玄学复杂度的话）
- 没了
嗯…真正有用的不过是前两条而已。
各种声明以及初始化
珂朵莉树的节点
应该是你要写珂朵莉树时首先要做的…
typedef bool type;
struct Node
{
unsigned int l;
unsigned int r;
mutable type data;
Node(unsigned int a, unsigned int b = 0, type c = 0);
bool operator <(const Node &a) const
{
return l < a.l;
}
};
Node::Node(unsigned int a, unsigned int b, type c)
{
l = a;
r = b;
data = c;
}
解释一下上面的代码。
-
珂朵莉树的
每一个节点代表着一个闭区间
，那么Node结构体里理应有这个区间的左右边界（即l和r）。 -
type和data是当前区间
统一的
类型与数值，就是说闭区间[l,r]内每个点的类型都是type（自己定义的，这里我使用了bool作为type，到底是什么无所谓），值都是data。（当然，我们只考虑离散的点） - data需要mutable修饰，这样我们可以在set中利用迭代器修改它。
- 对于结构体，我们自然需要构造函数，无需多讲。
- 由于我们使用set来存储Node，所以我们需要重载小于号，使其按照左端点排序。
构造珂朵莉树
#include <set>
set<Node> s;
没错这就完事了
就这么简单，你得到了一个没有初始化的珂朵莉树。
一般来说
，我们通过给定数据，向其中不断插入区间长度为1的区间来完成初始化。
比如形如这样的话：“第二行包括n个数，表示序列的初始状态”（摘自SCOI2010 序列操作）。
我们就可以这样初始化：
for (int i = 0; i < n; ++i)
{
static type temp = 0;
cin >> temp;
s.insert(Node(i, i, temp));
}
s.insert(Node(n, n, 0));
你的序列下标从0或者1开始是无所谓的。
这里有一个蜜汁细节，就是在把所有给定数据插入完成之后，需要在末尾多插入一个节点。我也不知道这究竟有啥用，根据自己测试貌似做不做这一步并没有什么区别，反正是玄学，信就完事了。
懒人宏定义
我个人并不是很懒，但是声明迭代器真的很令人痛苦。于是我选择了这样
#define S_IT set<Node>::iterator //S_IT = set_iterator
据我所知，这个宏定义是大部分写珂朵莉树的coder都选择了的。
你也可以自己搞一些更懒的宏定义。
至此，准备工作结束。
核心操作
分裂：split
既然我们要进行区间操作，那就得把这个区间
拿出来
（就是这么暴力的思想）
。
split(pos)操作将包含位置pos的区间[l,r]分裂成[l,pos-1]和[pos,r]，并返回后者的迭代器。
S_IT split(unsigned int pos)
{
S_IT it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos)
return it;
--it;
unsigned int l = it->l, r = it->r;
type data = it->data;
s.erase(it);
s.insert(Node(l, pos - 1, data));
return s.insert(Node(pos, r, data)).first;
}
我们先利用lower_bound()函数在set中查到左端点位置大于等于pos的节点。
如果这个节点的左端点位置正是pos，那么我们无需分裂，直接返回。
如果它的左端点位置不是pos，那么必然大于pos，则
包含位置pos的节点是上一个节点
，it-=1。
接下来的事情就好办了，暴力分裂再插入即可。不要忘了返回值。
此时，如果我们想使用区间[l,r]中的数据，只需要这么写：
S_IT it2 = split(r + 1), it1 = split(l);
for (; it1 != it2; ++it1)
{
； //利用迭代器it1搞些事情
}
这里有一个细节必须注意
，必须
先声明it2再声明it1
，否则根据split中的erase操作，迭代器it1
可能会
失效。（因为it1所属的节点可能被删除了）
区间赋值：assign
珂朵莉树最重要的操作，也是不让它退化为暴力算法的
玄学
保障。
既然一个区间内所有的值全都一样了，那么在珂朵莉树中这个区间就可以只用一个节点来表示
。这就是珂朵莉树的核心，光速降低节点数量的神器。
void assign(unsigned int l, unsigned int r, type val)
{
S_IT it2 = split(r + 1), it1 = split(l);
s.erase(it1, it2);
s.insert(Node(l, r, val));
return;
}
可见，这个区间里所有的节点全部被删除，使用
一个
新的节点来代替。
根据
我并不会的
证明，assign的区间长度
在随机数据下的期望
为N/3，十分恐怖。
而且这个assign在赋值之余还可以顺便做做区间统计啥的，根据情况而定
至此，珂朵莉树的核心操作介绍完毕。
附加的工作？
很多时候，一道题不可能只用两个函数就轻松搞定，需要额外的暴力函数与算法，是的就是暴力。
由于暴力算法大家肯定会，又怕大家不好理解，所以在这里贴一下我写的的
CF896C
的代码。
这道题虽说是起源，但是还是比较有难度的，认为太难的可以直接往下走，看另一个例子。
#include &l