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

珂朵莉树:学习笔记

老司机树,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;
	}
}

珂朵莉树就是这么暴力的一种数据结构,然而在一些涉及到很多次区间覆盖的问题中却能够跑的很快,果然还是 set 大法好啊……,下面是可以用珂朵莉树 AC 的题选

P.S:以下题目的正統解法几乎都是线段树,写法正确的线段树也通常比珂朵莉树跑的快一些

  1. SCOI2010 序列操作:珂朵莉树模板题,没什么好讲的
  2. SHOI2015 脑洞治疗仪:几乎是模板题,注意判断正常脑组织够不够填补脑洞即可
  3. LG2787 理理思维:模板题,输入字符串的时候尽量先把相同的字符合成一个结点
  4. LG4979 矿洞坍塌:模板题,注意输出字符串的优化和题目要求的判断条件即可

  5. USCAO1.2.1 挤牛奶:这个弱智题也需要用珂朵莉树?是的!只要是区间覆盖都可以用它骗分

附:珂朵莉美图欣赏

pic1

pic2

pic3

pic4

pic5