模拟 | 珂朵莉树：学习笔记

珂朵莉树：学习笔记

老司机树，ODT(Old Driver Tree)，又名珂朵莉树（Chtholly Tree)。

起源自 CF896C 。因为这是第一道以此树 AC 的题，又是关于动漫角色珂朵莉的，故因此得名。

是一种非常暴力的数据结构，时间复杂度不好计算，且取决于数据的随机性，珂朵莉树可以用于带有区间覆盖的问题当中，且当覆盖操作比较多的时候，它能发挥出一定优势，所以珂朵莉树通常用于写不出正统解法时的骗分选择

要保证珂朵莉树的复杂度正确，数据必须随机（也就是出题人不会特意卡），证明

在很多题目中不是正统的解法，但是有些时候却比正统的解法跑得更快……

核心思想

珂朵莉树的核心思想是：把值相同的区间合并成一个结点保存在 set 里面。

因此一个树节点只包含三个信息：左右端点 $L,R$ ，和区间值 $v$，定义时注意值 $v$ 要用 mutable 修饰

struct node{
    int L,R;
    mutable int v;
    node(int x, int y=-1, int z=0):L(x), R(y), v(z) {}
    bool operator<(const node& o)const{
        return L < o.L;
    }
};

~~其实核心思想就很暴力了……~~

一下是珂朵莉树的几种基本操作，无一例外地，实现它们的方式都非常暴力

关键操作：Split

split 是珂朵莉树的核心之一，用于从当前 set 中提取需要的区间结点便于操作，它会将一个大的区间结点 $[L,R]$ 分裂成两个区间结点，为 $[l,x-1]$ 和 $[x.R]$ ，一般情况下我们都会 split 两次，split(r+1);split(l)

注意一定要先 split(r+1)，之后我们会取得两个迭代器，这两个迭代器之间存储的就是操作区间内的结点了

而关于 split 的写法也比较简单，就是暴力找到以 $x$ 作为左端点的结点，然后把原来的大结点直接 erase 掉，新插入两个小结点，返回后一个结点的迭代器

#define se(X) set<X>::iterator
se(node) split(int pos){
	se(node) iter=s.lower_bound(node(pos));
	if(iter!=s.end() && iter->L==pos) return iter;
	iter--; int x=iter->L,y=iter->R; int z=iter->v;
	s.erase(iter); s.insert(node(x,pos-1,z));
	return s.insert(node(pos,y,z)).first;
}

关键操作：fill（assign）

assign 是珂朵莉树用于处理区间覆盖问题的操作，能减少 set 中的结点个数，区间覆盖操作越多，set 中的节点个数越少，因此每次操作的时间复杂度会降低，这也是珂朵莉树在某些题目中跑的比正统解法快的原因之一吧

assign 操作本身非常暴力，代码也很简洁，很好理解，就是先 split 得到覆盖的左右端点对应的迭代器，然后直接 erase 掉，插入一个新的结点……

#define se(X) set<X>::iterator
inline void fill(int l,int r,int d){
	se(node) iterr=split(r+1),iterl=split(l);
	s.erase(iterl,iterr);s.insert(node(l,r,d));
}

区间加：add

从区间加操作开始，以下操作全是基于 for 循环或 while 循环的纯暴力遍历来实现的

区间加法，就是 split 得到区间左右端点对应的迭代器，然后遍历这些区间，逐一加上就行了……

#define se(X) set<X>::iterator
inline void add(int l,int r,int d){
    se(node) iterr=split(r+1),iterl=split(l);
    for(;iterl!=iterr;iterl++) iterl->v+=d;
}

区间求和：sum

区间求和，也是先 split 然后再遍历，累加，注意中途要乘上区间长度，因为每个结点是一个值完全相同的区间

#define se(X) set<X>::iterator
ll sum(int l,int r){
	se(node) iterr=split(r+1),iterl=split(l);
	ll ans=0;
	while(iterl!=iterr)
		ans=(ans+(ll)(iterl->R-iterl->L+1)*iterl->v,
		iterl++;
	return ans;
}

区间第K小：kth

个人感觉这是最暴力的操作了，因为这个操作不但遍历，而且中途还直接使用 vector 排序，计算的时候也要遍历 vector……

int kth(int l,int r,int k){
    #define se(X) set<X>::iterator
    typedef pair<int,int> pr;
	vector<pr> X;
	se(node) iterr=split(r+1),iterl=split(l);
	while(iterl!=iterr) X.push_back(make_pair(iterl->v,iterl->R-iterl->L+1)),iterl++;
	sort(X.begin(),X.end());
	for(ve(pr) iter=X.begin();iter!=X.end();iter++){
		k-=iter->second;if(k<=0) return iter->first;
	}
}