浅谈珂朵莉树

序言

珂朵莉是世界上最幸福的女孩。

(~)

珂朵莉树是？

​ 老司机树（Old Driver Tree），起源于 CF896C 。出题人 ODT 发明并命名，又名珂朵莉树（Chtholly Tree）。

(~)

在学珂朵莉树之前，需要会些啥？

​ 需要会 ( ext{C++STL}) 的 ( ext{set}) ，在这里博主就简单普及一下 ( ext{set}) 吧。

1. ( ext{set}) 维护的是个不可重集。
2. ( ext{set}) 维护的元素是有序的。

​ ( ext{set}) 的内部实现是一棵红黑树（平衡树中速度较快），因此性能不赖。

(~)

( ext{set}) 的声明 :

set<数据类型>名字;
/* for example */
set<int>a;
set< pair<int,int> >b;
struct Node{...}; set<Node>c;

(~)

( ext{set}) 的迭代器 :

​ ( ext{set}) 的迭代器不支持随机访问，只能支持 " ++ " 和 " -- " 来操作迭代器，来看这个片段：

set<int>::iterator it;

​ 此时这里的 it 就是迭代器，为了方便，我们常常使用宏定义 #define iter set<数据类型>::iterator ，当然在 ( ext{C++11}) 下可以直接使用 auto 来代替 iter 。

​ 如果 it 是迭代器，那么调用 it++ 会使得 it 指向其在 ( ext{set}) 中的下一个元素，也就是说，若原本 it 在 ( ext{set}) 中的排名为 (k) ，则调用 it++ 会使得 it 指向排名为 (k+1) 的元素。it-- 同理，指向上一个元素。

​ " ++ " 和 " -- " 时间复杂度都是 (mathcal{O(log n)}) 的。

(~)

( ext{set}) 的插入 :

​ 例如我们有一个 ( ext{set}) 叫做 (S) 。

​ S.insert(x) 用 (mathcal{O(log n)}) 的时间将 (x) 插入到 (S) 中，若 (S) 已经维护了 (x) ，则不会重复插入 (x) ，也就是对 (S) 无影响。

S.insert(x);
/* for example */
set< pair<int,int> >S; S.insert(make_pair(x,y));
struct Node{int l,r,v;}; set<Node>S; S.insert((Node){1,n,114514});

(~)

( ext{set}) 的删除 :

​ 例如我们有一个 ( ext{set}) 叫做 (S) 。

​ 若 it 是个迭代器，则 S.erase(it) 用 (mathcal{O(log n)}) 的时间将 it 指向的元素删去。

​ 若 (x) 是个元素，则 S.erase(x) 用 (mathcal{O(log n)}) 的时间将元素 (x) 删去，若 (S) 没有维护 (x) ，则不会删除 (x) ，也就是对 (S) 无影响。

S.erase(it);
S.erase(x);
/* for example */
set< pair<int,int> >S; S.erase(make_pair(x,y));
struct Node{int l,r,v;}; set<Node>S; S.erase((Node){1,n,114514});

(~)

( ext{set}) 的查找 :

​ 例如我们有一个 ( ext{set}) 叫做 (S) 。

​ S.find(x) 用 (mathcal{O(log n)}) 的时间查找元素 (x) ，并返回该元素的迭代器，若元素 (x) 不存在，返回 S.end() 。

​ S.lower_bound(x) 用 (mathcal{O(log n)}) 的时间查找大于等于元素 (x) 中最小的一个，并返回指向该元素的迭代器，若不存在，返回 S.end() 。

​ S.upper_bound(x) 用 (mathcal{O(log n)}) 的时间查找大于元素 (x) 中最小的一个，并返回该元素的迭代器，若不存在，返回 S.end() 。

S.find(x);
S.lower_bound(x);
S.upper_bound(x);
/* for example */
set< pair<int,int> >S; it=S.find(make_pair(x,y));
struct Node{int l,r,v;}; set<Node>S; it=S.upper_bound((Node){1,n,114514});

(~)

至此 ( ext{set}) 的操作已经可以用来编写珂朵莉树了。

珂朵莉树还有链表的实现方法，学有余力的读者可以自己去了解一下。

(~)

正式了解一下珂朵莉树！

​ 珂朵莉树维护的是一堆三元组 ((l,r,val)) ，其含义是：区间 ([l,r]) 的值均为 (val) 。用 ( ext{set}) 维护这一堆三元组（按区间顺序排序）。

​ 我们发现珂朵莉树的精髓在于：把一段值相同的区间缩成一个三元组处理。

(~)

珂朵莉树的声明 :

struct Node{
    int l,r;
    mutable int val;
    Node(int a,int b,int c):l(a),r(b),val(c){}
    inline bool operator < (const Node a) const {
        return l<a.l;
	}
}
set<Node>odt;

(~)

split 操作 :

​ 有时候，我们想要对一段区间 ([l,r]) 进行操作或者查询，我们希望正好有若干个段刚好覆盖了区间 ([l,r]) ，这样我们就可以直接在这些段上面操作了。

​ 但是考虑到 (l) 和 (r) 所在的段，以 (l) 为例子，我们设 (l) 所在的段为 ([x,y]) ，我们会发现，只有 ([l,y]) 这个段是有用的，而我们不需要对 ([x,l)) 这个段进行任何处理。但是人家两个段偏偏却合在一起，组成了段 ([x,y]) ！此时我们就要想办法，将段 ([x,y]) 拆成段 ([x,l)) 和段 ([l,y]) 。

​ 设函数 (split(x)) 表示：将 (x) 所在的段 ([L,R]) 拆成段 ([L,x)) 和段 ([x,R]) ，并返回段 ([x,R]) 的迭代器。

1. 二分查找 (x) 在 ( ext{set}) 里面所在段的迭代器。
2. 判断该段的左端点 (L) 是否与 (x) 重叠，若有，则代表不存在段 ([L,x)) ，直接返回该迭代器；否则进入 3 。
3. 删除该迭代器所指向的元素，插入两个三元组 ((L,x-1,val)) 与 ((x,R,val)) ，并返回 ((x,R,val)) 的迭代器。

iter split(int x)
{
	if(x>n)return odt.end(); // 特判
	iter it=--odt.upper_bound((Node){x,0,0});
	if(it->l==x)return it;
	int L=it->l,R=it->r,val=it->val;
	odt.erase(it);
	odt.insert((Node){L,x-1,val});
	return odt.insert((Node){x,R,val}).first;
}

(~)

assign 操作 :

​ 最最最最最最重要的操作：区间推平。

​ 区间推平操作可以使得 ODT 的数据规模迅速减小，是保证复杂度的关键所在，设想一下，我们将整个序列 ([1,n]) 推平为 (1) ，那么整个 (set) 只需要维护一个三元组 ((1,n,1)) 就可以起到维护的作用了。

​ 设函数 (assign(l,r,val)) 表示：将区间 ([l,r]) 推平为 (val) 。

1. 令 (itr=split(r+1),itl=split(l)) 。
2. 删除 (itl) 到 (itr) 之间的所有元素（不含 (itr)）。
3. 插入三元组 ((l,r,val)) 。

void assign(int l,int r,int val)
{
	iter itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert((Node){l,r,val});
}

(~)

其他操作 :

​ 其他操作其实也都差不多辣，例如区间加啥的，都可以搞。

iter itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++)
{
    // do what you want.
}

​ 当然这个板子不是万能的，需要根据情况应变。

(~)

由上述内容可知，珂朵莉树其实并不算一个标准的树形数据结构，但是为啥叫它珂朵莉 " 树 " 呢？

因为珂朵莉树用 set 维护，而 set 内部实现是一棵红黑树。

(~)

珂朵莉树可以干什么呢？

​ 骗分。

​ 骗分？

​ 骗分！

​ 对的，你没有看错，就是骗分。

​ 若一个数据结构题，带有区间推平操作，都可尝试使用 ODT 来骗分，虽说 ODT 这种东西随便卡的。例如数据里根本没有区间推平操作，再构造 (n) 个长度为 (1) 的段，然后全是询问操作，这样的话 ODT 连暴力都不如。

​ 若想要保证时间复杂度正确，必要的条件是 " 数据随机 " ，附 证明1 与 证明2，在数据随机的情况下，时间复杂度为 (mathcal{O(n log log n)})，若改为链表维护，则时间复杂度为 (mathcal{O(n log n)})。

​ 有良心的出题人一般都会给你设置一档 " 数据随机 " 的部分分。

​ 总之使用 ODT 还是谨慎一点好。

(~)

好题选讲

​ 通过几道题来帮助大家深入理解 ODT 。

---

CF896C Willem, Chtholly and Seniorious

[ exttt{Description} ]

维护一个长度为 (n) 的数列，支持 (4) 种操作：

• 1 l r x 将 (a_l,a_{l+1},...,a_{r-1},a_r) 加上 (x) 。

• 2 l r x 将 (a_l,a_{l+1},...,a_{r-1},a_r) 改为 (x) 。

• 3 l r x 询问区间 ([l,r]) 的第 (x) 小。

• 4 l r x y 询问 ((sumlimits_{i=l}limits^{r}{a_i}^x) ext{mod} y) 。

数据由给定的伪代码生成。

[ exttt{Solution} ]

• 这题是起源题，在这里致敬出题人 ODT （感谢 + 膜拜）。

• " 数据由给定的伪代码生成 " 暗示了什么？数据随机！我们还发现操作 (2) 是熟悉的区间推平操作。

• 所以这道题是个可以用 ODT 来解决的标准样式（区间推平 + 数据随机）。

• 对于操作 1 l r x ，我们调用 itr=split(r+1),itl=split(l) ，将区间 ([l,r]) 拆出来，然后令 (itl) 到 (itr) 指向的元素的值（第三维 (val)）加上 (x) 。

• 对于操作 2 l r x ，基本操作，不多说了。

• 对于操作 3 l r x ，我们调用 itr=split(r+1),itl=split(l) ，将区间 ([l,r]) 拆出来，然后依次扫描 (itl) 到 (itr) ，将指向元素缩成一个二元组 ((val,size)) 存进一个 ( ext{STLvector}) 里，这里的第一维 (val) 就是该元素维护的值，第二维 (size) 就是该元素维护的区间的区间大小（(r-l+1)），扫描完成后，将该 ( ext{STLvector}) 按第一维 (val) 从小到大排序，然后依次扫描这些二元组 ((val,size)) ：

  1. 若 (kleq size) ，说明答案就是当前的 (val) ，返回 (val) 的值即可。
  2. 若 (k>size) ，说明答案应该比当前的 (val) 还要大，令 (k-=size) ，然后继续扫描。

  最后切记要清空这个 ( ext{STLvector}) 。

• 对于操作 4 l r x y ，我们调用 itr=split(r+1),itl=split(l) ，将区间 ([l,r]) 拆出来，考虑到对于底数相等的数，幂不变，所以我们考虑任意一个三元组 ((l,r,val)) ，它对答案有 ((r-l+1) imes val^x) 的贡献，于是我们就可以依次扫描 (itl) 到 (itr) ，将指向元素对答案的贡献累加进答案中，扫描完即可求出答案了，求幂的过程使用快速幂。

• 至此此题得到解决。

[ exttt{Code} ]

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>

#define RI register int
#define iter set<Node>::iterator

using namespace std;

int power(long long a,int b,int p)
{
	a%=p;
	int ans=1;
	for(;b;b>>=1)
	{
		if(b&1)ans=1ll*ans*a%p;
		a=1ll*a*a%p;
	}
	return ans;
}

long long seed;
int MaxV;

long long rnd()
{
	long long res=seed;
	seed=(seed*7+13)%(1000000007);
	return res;
}

int n,m;

struct Node{
	int l,r;
	mutable long long val;
	Node(int a,int b,long long c):l(a),r(b),val(c){};
	inline bool operator < (const Node a) const {
		return l<a.l;
	}
};

set<Node>odt;

iter split(int x)
{
	if(x>n)return odt.end();
	iter it=--odt.upper_bound((Node){x,0,0});
	if(it->l==x)return it;
	int l=it->l,r=it->r; long long val=it->val;
	odt.erase(it);
	odt.insert((Node){l,x-1,val});
	return odt.insert((Node){x,r,val}).first;
}

void add(int l,int r,int val)
{
	iter itr=split(r+1),itl=split(l);
	for(;itl!=itr;itl++)
		itl->val+=val;
}

void assign(int l,int r,int val)
{
	iter itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert((Node){l,r,val});
}

long long ask_kth(int l,int r,int k)
{
	vector< pair<long long,int> >QAQ;
	iter itr=split(r+1),itl=split(l);
	for(;itl!=itr;itl++)
		QAQ.push_back(make_pair(itl->val,itl->r-itl->l+1));
	sort(QAQ.begin(),QAQ.end());
	for(RI i=0;i<(int)QAQ.size();i++)
	{
		if(k<=QAQ[i].second)return QAQ[i].first;
		else k-=QAQ[i].second;
	}
	return -1;
}

int ask_xpower(int l,int r,int x,int y)
{
	iter itr=split(r+1),itl=split(l);
	int ans=0;
	for(;itl!=itr;itl++)
		ans=(ans+1ll*(itl->r-itl->l+1)*power(itl->val,x,y))%y;
	return ans;
}

int main()
{
	scanf("%d%d%lld%d",&n,&m,&seed,&MaxV);

	for(RI i=1;i<=n;i++)
		odt.insert((Node){i,i,rnd()%MaxV+1});

	while(m--)
	{
		int opt=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y;

		if(l>r)
			swap(l,r);

		if(opt==3)
			x=(rnd()%(r-l+1))+1;
		else
			x=(rnd()%MaxV)+1;

		if(opt==4)
			y=(rnd()%MaxV)+1;

		switch(opt)
		{
			case 1:{

				add(l,r,x);

				break;
			}

			case 2:{

				assign(l,r,x);

				break;
			}

			case 3:{

				printf("%lld
",ask_kth(l,r,x));

				break;
			}

			case 4:{

				printf("%d
",ask_xpower(l,r,x,y));

				break;
			}
		}
	}

	return 0;
}

---

[SCOI2010]序列操作

[ exttt{Description} ]

维护一个长度为 (n) 的 (0/1) 序列，支持 (5) 种操作：

• 0 l r 将区间 ([l,r]) 的所有数改为 (0) 。

• 1 l r 将区间 ([l,r]) 的所有数改为 (1) 。

• 2 l r 将区间 ([l,r]) 的所有数取反（(0) 变 (1) ，(1) 变 (0)）。

• 3 l r 询问区间 ([l,r]) 有多少个 (1) 。

• 4 l r 询问区间 ([l,r]) 最多有多少个连续的 (1) 。

[ exttt{Solution} ]

• 我们发现操作 0 l r 和 1 l r 都是区间推平操作，虽说不保证数据随机，ODT 是假的，但是还是可以通过这题练练 ODT 的。

• 对于操作 0 1 r 和 1 l r ，基本操作，不多说了。

• 对于操作 2 l r ，我们调用 itr=split(r+1),itl=split(l) ，将区间 ([l,r]) 拆出来，然后依次扫描 (itl) 到 (itr) ，将三元组 ((l,r,val)) 赋为 ((l,r,val ext{xor} 1)) ，即可取反。

• 对于操作 3 l r ，我们调用 itr=split(r+1),itl=split(l) ，将区间 ([l,r]) 拆出来，然后依次扫描 (itl) 到 (itr) ，考虑一个三元组 ((l,r,val)) ，若 (val) 为 (1) ，则该三元组对答案有 (r-l+1) 贡献，否则贡献为 (0) 。依次计算每个三元组的贡献即可。

• 对于操作 4 l r ，我们调用 itr=split(r+1),itl=split(l) ，将区间 ([l,r]) 拆出来。考虑到最后答案的连续的 "(1)" 段，定是由 ODT 中若干个连续的节点组成，且这些节点的第三维 (val) 都为 (1) 。具体的，我们记一个变量 (sum) ，若当前扫描到的三元组 ((l,r,val)) 的第三维 (val) 为 (1) ，则令 (sum+=r-l+1) ，否则我们就尝试用 (sum) 去更新答案，再把 (sum) 清 (0) ，扫描完即可求出答案了。

• Luogu 管理员加强了数据，卡了 ODT ，在 Luogu 已经过不了了，只能拿到 30pts ......

[ exttt{Code} ]

#include<cstdio>
#include<algorithm>
#include<set>

#define RI register int
#define iter set<Node>::iterator

using namespace std;

inline int read()
{
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}

const int N=100100;

int n,m;

int a[N];

struct Node{
	int l,r;
	mutable int val;
	Node(int a,int b,int c):l(a),r(b),val(c){}
	inline bool operator < (const Node a) const {
		return l<a.l;
	}
};

set<Node>odt; 

iter split(int x)
{
	if(x>n)return odt.end();
	iter it=--odt.upper_bound((Node){x,0,0});
	if(it->l==x)return it;
	int l=it->l,r=it->r,val=it->val;
	odt.erase(it);
	odt.insert((Node){l,x-1,val});
	return odt.insert((Node){x,r,val}).first;
}

void assign(int l,int r,int val)
{
	iter itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert((Node){l,r,val}); 
}

void reverse(int l,int r)
{
	iter itr=split(r+1),itl=split(l);
	for(;itl!=itr;itl++)
		itl->val^=1;
}

int ask_cnt(int l,int r)
{
	iter itr=split(r+1),itl=split(l);
	int ans=0;
	for(;itl!=itr;itl++)
		if(itl->val==1)
			ans+=itl->r-itl->l+1;
	return ans;
}

int ask_wmax(int l,int r)
{
	iter itr=split(r+1),itl=split(l);
	int ans=0,sum=0;
	for(;itl!=itr;itl++)
		if(itl->val==1)
			sum+=itl->r-itl->l+1;
		else
			ans=max(ans,sum),sum=0;
	ans=max(ans,sum);
	return ans;
}

int main()
{
	n=read(),m=read();

	for(RI i=1;i<=n;i++)
		a[i]=read();

	for(RI i=1;i<=n;i++)
		odt.insert((Node){i,i,a[i]});

	while(m--)
	{
		int opt=read(),l=read()+1,r=read()+1;

		switch(opt)
		{
			case 0:{

				assign(l,r,0);

				break;
			}

			case 1:{

				assign(l,r,1);

				break;
			}

			case 2:{

				reverse(l,r);

				break;
			}

			case 3:{

				printf("%d
",ask_cnt(l,r));

				break;
			}

			case 4:{

				printf("%d
",ask_wmax(l,r));

				break;
			}
		}
	}

	return 0;
}

---

[SHOI2015]脑洞治疗仪

[ exttt{Description} ]

维护一个长度为 (n) 的 (0/1) 序列，支持 (3) 种操作：

• 0 l r 将区间 ([l,r]) 的所有数改为 (0) 。
• 1 l0 r0 l1 r1 将区间 ([l_0,r_0]) 的所有 "(1)" 填到区间 ([l_1,r_0]) 的 "(0)" 上（位置靠前的优先填，多余 (1) 弃掉）。
• 2 l r 询问区间 ([l,r]) 最多有多少连续的 (0) 。

[ exttt{Solution} ]

• 注意到操作 0 l r ，又是区间推平操作，于是我们又可以用 ODT 骗分了

• 对于 0 l r ，基本操作，不多说了。

• 对于 1 l0 r0 l1 r1 ，我们先统计出区间 ([l_0,r_0]) 的 "(1)" 个数，记为 (cnt) ，随后将区间 ([l_0,r_0]) 推平为 (0) 。接下来是填数部分，调用 itr=split(r1+1),itl=split(l1) ，将区间 ([l_1,r_1]) 拆出来，然后依次扫描 (itl) 到 (itr) ，考虑当前扫描到的三元组 ((l,r,val)) ，若 (val) 为 (1) ，则继续扫描，否则，记 (size=r-l+1)：

  1. 若 (cnt=0) ，则不能继续填数了，直接退出。
  2. 若 (cnt<size) ，则说明我们只能填该段的一部分（前 (cnt) 个数），那我们调用 it=--split(l+cnt) ，就分出了该区间的前 (cnt) 个数，将 (it) 指向的元素的第三维 (val) 改为 (1) ，然后退出即可。
  3. 若 (size leq cnt) ，则说明剩下的 "(1)" 的个数足够填满这个段，把该段的第三维 (val) 改为 (1) ，然后我们再令 (cnt-=size) ，继续扫描。

• 对于 2 l r ，上一个例题已经详细讲过了，不多说了。

• 这题 Luogu 管理员居然没有去卡 ODT ，谢天谢地。

[ exttt{Code} ]

#include<cstdio>
#include<algorithm>
#include<set> 

#define RI register int
#define iter set<Node>::iterator

using namespace std;

namespace IO
{
    static char buf[1<<20],*fs,*ft;
    inline char gc()
    {
        if(fs==ft)
        {
			ft=(fs=buf)+fread(buf,1,1<<20,stdin);
			if(fs==ft)return EOF;
        }
        return *fs++;
    }
    #define gc() getchar()
	inline int read()
	{
		int x=0,f=1;char s=gc();
		while(s<'0'||s>'9'){if(s=='-')f=-f;s=gc();}
		while(s>='0'&&s<='9'){x=x*10+s-'0';s=gc();}
		return x*f;
	}
}using IO::read;

const int N=200100;

int n,m;

struct Node{
	int l,r;
	mutable bool val;
	Node(int a,int b,int c):l(a),r(b),val(c){}
	inline bool operator < (const Node a) const {
		return l<a.l;
	}
};

set<Node>odt;

iter split(int x)
{
	if(x>n)return odt.end();
	iter it=--odt.upper_bound((Node){x,0,0});
	if(it->l==x)return it;
	int l=it->l,r=it->r; bool val=it->val;
	odt.erase(it);
	odt.insert((Node){l,x-1,val});
	return odt.insert((Node){x,r,val}).first;
}

void assign(int l,int r,int val)
{
	iter itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert((Node){l,r,val});
}

void trans(int l0,int r0,int l1,int r1)
{
	iter itr0=split(r0+1),itl0=split(l0);
	int cnt=0;
	for(iter i=itl0;i!=itr0;i++)
		if(i->val)cnt+=i->r-i->l+1;
	odt.erase(itl0,itr0);
	odt.insert((Node){l0,r0,0});
	iter itr1=split(r1+1),itl1=split(l1);
	for(iter i=itl1;i!=itr1;i++)
	{
		if(i->val)continue;
		if(i->r-i->l+1<=cnt)
			i->val=true,cnt-=i->r-i->l+1;
		else
		{
			if(cnt)
			{
				iter it=--split(i->l+cnt);
				it->val=true;
			}
			break;
		}
	}
}

int ask_wmax(int l,int r)
{
	iter itr=split(r+1),itl=split(l);
	int ans=0,sum=0;
	for(;itl!=itr;itl++)
		if(itl->val)
			ans=max(ans,sum),sum=0;
		else
			sum+=itl->r-itl->l+1;
	return max(ans,sum);
}

int main()
{
	n=read(),m=read();

	odt.insert((Node){1,n,1});

	while(m--)
	{
		int opt=read(),l=read(),r=read(),l1,r1;

		switch(opt)
		{
			case 0:{

				assign(l,r,0);

				break;
			}

			case 1:{

				l1=read(),r1=read();

				trans(l,r,l1,r1);

				break;
			}

			case 2:{

				printf("%d
",ask_wmax(l,r));

				break;
			}
		}
	}

	return 0;
}

---

（可能还会有题，先挖个坑。

---

(~)

结语

​ 正如上文提及到的，珂朵莉树是一个强大的骗分算法，若有一道数据结构题，满足 " 带有区间推平 " 和 " 数据随机 " ，这两个条件，则珂朵莉树是一个不二的选择。

​ 总之使用珂朵莉树需谨慎，毕竟这玩意可以随便卡的。

​ 希望博主的这篇文章对大家有帮助。

[ exttt{Thanks} exttt{for} exttt{watching} ]