浅谈珂朵莉树 - 算法学习 | 123hh2 = Keep moving forward

# 珂朵莉树！

先放个链接：クトリ！

最近模拟赛考的都好奇怪， $T1$ 怎么想都没想到居然是建 $26$ 颗权值线段树然后瞎勾⑧跑就能过，但好像都跑的挺慢的，然后我去搜题解，发现居然能 $TM$ 用珂朵莉树水过去？？？

水个 p，直接拿了个第二优解

$Renamoe$ 常数超小 %%%

然后贺完题解的我并不知道珂朵莉树到底怎么写，于是就拿出了一部分的颓废时间来学习这个毒瘤珂爱的数据结构

以上吹水言论应该全部删除！（

下面进入正题

首先我们先看珂朵莉树的经典例题 CF896C，珂朵莉树就是在这场比赛中诞生的

# 题目大意

要求我们写一个毒瘤数据结构，可以支持

1 $l,r,x$ : 将 $[l,r]$ 区间全部加上 $x$
2 $l,r,x$ : 将 $[l,r]$ 区间全都赋值为 $x$
3 $l,r,x$ : 输出将 $[l,r]$ 区间从小到大排序后的第 $x$ 个数是的多少 (即区间第 $x$ 小，数字大小相同算多次，保证 $1 \le x \le r-l+1$ )
4 $l,r,x$ : 输出 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值 (即 $\sum^{r}_{i=l} a^{x}_{i})\mod y$ )

乍一看可以用主席树套线段树写（我不知道对不对，我瞎想的）

但是由于本人太菜了，不会写，并且今天学习的主题是珂朵莉树，所以我们就用珂朵莉树来写这道题

首先我们需要一个的东西： $set$ ，因为珂朵莉树就是基于 $set$ 实现的

那么我们这个 $set$ 集合里都存些什么呢？

我们在一个序列上进行区间操作，首先肯定能想到会有左端点右端点和修改值对不对？

所以我们的结构体里存放的是当前这个集合里的左端点 $l$ ，右端点 $r$ 和当前区间存的权值

你可能会很好奇，当前区间的权值要怎么存？难道要一个一个存吗？

当然不！我们的集合的的权值表示的是这个集合包括的区间里所有的数的权值

所以每一个集合维护了一个序列上的相同区间的权值和该区间的左右端点

那么假设我们的序列的数各不相同或者是不连续的该怎么办？这样子的话我们的集合会开到 $n$ 个，这不就跟暴力一样了吗？（其实比暴力更慢）

我们注意到这一个操作：

2 $l,r,x$ : 将 $[l,r]$ 区间全都赋值为 $x$

这个操作其实就是在帮我们降低珂朵莉树的复杂度，因为将一段区间赋值为相同的数，就相当于将这一段区间中的集合全都并起来揉成一个区间了

PS：有关珂朵莉树复杂度的证明 Codeforces 上关于珂朵莉树的复杂度的证明

好，接下来给出结构体代码

	// 珂朵莉树基于 set
	// 开一个集合，每个集合用一个结构体 A 表示
	// 结构体 A 里存放的分别是 l：目前这一段区间的左端点
	//r：目前这一段区间的右端点
	//val：目前这一区间的每个元素的值，这段区间的元素的值一定都是相等的
	// 发现 val 带了一个前缀 mutable，意为可变的
	// 因为我们可能会随时更改某一区间的元素值
	struct A
	{
	long long l,r;mutable long long val;
	bool operator <(const A &now) const{return l<now.l;}
	// 保证集合是按区间从左往右排序好了的
	A(long long nowl,long long nowr,long long nowval) :l(nowl),r(nowr),val(nowval) {}
	A(long long nowl) :l(nowl) {}
	};//set 里的结构体
	set<A> s;

好，我们的珂朵莉树已经建完了！就下来的操作相信聪明的你一定能够写出来，现在就去试试吧！ CF896C（雾

接下来我们依次考虑题目中给的每个操作

1 $l,r,x$ : 将 $[l,r]$ 区间全部赋值为 $x$

我们应该怎样在我们的集合中操作呢？

下面介绍一个暴力的函数 --- $split$

它将当前 $pos$ 所在的集合暴力拆分成两个集合

其对应的区间分别是 $[l,pos-1]$ ， $[pos,r]$ ，然后我们返回后一个集合对应的指针进行操作

为什么是后一个集合？废话因为后边的集合包括了你当前需要进行操作的 $pos$

# 下面给出 $split$ 代码

	set<A>::iterator split(long long pos)// 核心操作 split 用来分裂集合用的
	{
	set<A>::iterator it=s.lower_bound(A(pos));// 查找当前位置在哪个集合中
	if(it!=s.end()&&it->l==pos) return it;// 找到了直接返回
	it--;// 这样的话找到了 s.end () 到头了或者是恰好大于等于上一个集合的 r，往回跳一个就是了
	long long l=it->l,r=it->r,val=it->val;// 把当前集合的信息提取出来
	s.erase(it);// 删掉这个集合
	// 下面将这个集合分裂成两个集合
	// 区间分别为 l->pos-1 和 pos->r
	s.insert(A(l,pos-1,val));
	return s.insert(A(pos,r,val)).first;// 返回后一个集合的指针，因为我们的 pos 包含在了这个集合中
	}

这样我们就能实现集合之间的暴力拆了

那么你可能就想到了一个问题

如果这个集合一直分裂下去，迟早有一天会分裂成一个个小集合，那不比暴力还暴力吗？

所以

2 $l,r,x$ : 将 $[l,r]$ 区间全部赋值为 $x$

就是一个重要的操作了，这个操作可以让我们将一些零散的集合重新合并成一个大集合

# 那么我们写一个对应的函数来实现这个操作，函数命名为 $assign$

	void assign(long long l,long long r,long long val)// 另一个核心操作，用于降低珂朵莉树的复杂度和进行区间赋值操作
	{
	set<A>::iterator it2=split(r+1),it1=split(l);// 将我要赋值的区间的端点所对应的集合指针找出来
	// 为什么先找 r+1，再找 l？
	// 因为 split 中有删除和添加操作，如果我先找 l，那么必定会对后续找 r+1 影响，从而 WA 或 RE
	// 而先找 r+1 再找 l 就不会出现这样的问题了
	s.erase(it1,it2);// 将这一段区间里的所有集合统统清除！
	s.insert((A){l,r,val});// 加入一个大集合表示 l 到 r 的权值全是 val
	}

好了，区间赋值操作我们也搞好了，这道题我们就基本快完成了（因为这两个函数是珂朵莉树的核心操作）

# 接下来看区间加的操作

1 $l,r,x$ : 将 $[l,r]$ 区间全部加上 $x$

	void add(long long l,long long r,long long val)// 区间赋值操作
	{
	set<A>::iterator it2=split(r+1),it1=split(l);// 暴力拆集合
	for(set<A>::iterator it=it1;it!=it2;it++) it->val+=val;// 暴力加值
	// 总结：简单粗暴 qwq
	}

没什么好说的，将 $[l,r]$ 区间通过 $split$ 操作暴力拆出来，然后再把这个区间里的所有集合所表示的值全都加上 $val$ 就好了

# 求区间第 $K$ 小

3 $l,r,x$ : 输出将 $[l,r]$ 区间从小到大排序后的第 $x$ 个数是的多少 (即区间第 $x$ 小，数字大小相同算多次，保证 $1 \le x \le r-l+1$ )

	long long get_kth(long long l,long long r,long long k)// 求区间第 K 小
	{
	set<A>::iterator it2=split(r+1),it1=split(l);// 还是暴力拆区间
	vector<pair<long long,long long> > q;q.clear();// 开个 vector 存当前区间里集合的值和其对应的区间长度
	for(set<A>::iterator it=it1;it!=it2;it++) q.push_back(pair<long long,long long>(it->val,it->r-it->l+1));// 存起来！
	sort(q.begin(),q.end());// 默认按照 pair 第一个元素从小到大排序
	for(ri long long i=0;i<q.size();i++)// 正序遍历求第 K 小
	{
	k-=q[i].second;// 每次减掉这个区间的长度
	if(k<=0) return q[i].first;// 小于等于 0 了说明这个区间里包含了我们要查询的第 K 小值，直接返回就好了
	}
	}

也是暴力的拆集合，然后把当前区间里包含的集合全部掏出来排个序，然后暴力求个第 $K$ 小就好了

# 最后一个操作，求区间每个数的 $x$ 次幂模 $y$ 的和

	inline long long fstpow(long long n,long long m,long long md)// 快速幂，别傻到暴力求 x 次幂（
	{
	long long ans=1ll,base=n;base%=md;
	while(m)
	{
	if(m&1) ans*=base,ans%=md;
	base*=base,base%=md,m>>=1;
	}
	return ans;
	}
	long long query(long long l,long long r,long long x,long long y)
	{
	long long ans=0;
	set<A>::iterator it2=split(r+1),it1=split(l);// 依旧暴力拆区间
	// 对于每个集合，暴力求和
	for(set<A>::iterator it=it1;it!=it2;it++) ans+=fstpow(it->val,x,y)*(it->r-it->l+1),ans%=y;
	return ans;
	}

$OK$ 到此，我们已经把这道题所有的关键操作写完了，下面上一下整体代码

	#include<bits/stdc++.h>
	#define ri register
	using namespace std;
	inline long long read()
	{
	long long x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	inline void write(long long x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const long long mod=1e9+7,maxn=1e5+1;
	long long n,m,seed,vmax,awa[maxn];
	inline long long myrand() {long long ret=seed;seed=(seed*7ll+13ll)%mod;return ret;}
	// 珂朵莉树基于 set
	// 开一个集合，每个集合用一个结构体 A 表示
	// 结构体 A 里存放的分别是 l：目前这一段区间的左端点
	//r：目前这一段区间的右端点
	//val：目前这一区间的每个元素的值，注意这段区间的元素的值一定都是相等的
	// 发现 val 带了一个前缀 mutable，意为可变的
	// 因为我们可能会随时更改某一区间的元素值
	struct A
	{
	long long l,r;mutable long long val;
	bool operator <(const A &now) const{return l<now.l;}
	// 保证集合是按区间从左往右排序好了的
	A(long long nowl,long long nowr,long long nowval) :l(nowl),r(nowr),val(nowval) {}
	A(long long nowl) :l(nowl) {}
	};//set 里的结构体
	set<A> s;
	set<A>::iterator split(long long pos)// 核心操作 split 用来分裂集合用的
	{
	set<A>::iterator it=s.lower_bound(A(pos));// 查找当前位置在哪个集合中
	if(it!=s.end()&&it->l==pos) return it;// 找到了直接返回
	it--;// 这样的话找到了 s.end () 到头了或者是恰好大于等于上一个集合的 r，往回跳一个就是了
	long long l=it->l,r=it->r,val=it->val;// 把当前集合的信息提取出来
	s.erase(it);// 删掉这个集合
	// 下面将这个集合分裂成两个集合
	// 区间分别为 l->pos-1 和 pos->r
	s.insert(A(l,pos-1,val));
	return s.insert(A(pos,r,val)).first;// 返回后一个集合的指针，因为我们的 pos 包含在了这个集合中
	}
	void assign(long long l,long long r,long long val)// 另一个核心操作，用于降低珂朵莉树的复杂度和进行区间赋值操作
	{
	set<A>::iterator it2=split(r+1),it1=split(l);// 将我要赋值的区间的端点所对应的集合指针找出来
	// 为什么先找 r+1，再找 l？
	// 因为 split 中有删除和添加操作，如果我先找 l，那么必定会对后续找 r+1 影响，从而 WA 或 RE
	// 而先找 r+1 再找 l 就不会出现这样的问题了
	s.erase(it1,it2);// 将这一段区间里的所有集合统统清除！
	s.insert((A){l,r,val});// 加入一个大集合表示 l 到 r 的权值全是 val
	}
	void add(long long l,long long r,long long val)// 区间赋值操作
	{
	set<A>::iterator it2=split(r+1),it1=split(l);// 暴力拆集合
	for(set<A>::iterator it=it1;it!=it2;it++) it->val+=val;// 暴力加值
	// 总结：简单粗暴 qwq
	}
	long long get_kth(long long l,long long r,long long k)// 求区间第 K 小
	{
	set<A>::iterator it2=split(r+1),it1=split(l);// 还是暴力拆区间
	vector<pair<long long,long long> > q;q.clear();// 开个 vector 存当前区间里集合的值和其对应的区间长度
	for(set<A>::iterator it=it1;it!=it2;it++) q.push_back(pair<long long,long long>(it->val,it->r-it->l+1));// 存起来！
	sort(q.begin(),q.end());// 默认按照 pair 第一个元素从小到大排序
	for(ri long long i=0;i<q.size();i++)// 正序遍历求第 K 小
	{
	k-=q[i].second;// 每次减掉这个区间的长度
	if(k<=0) return q[i].first;// 小于等于 0 了说明这个区间里包含了我们要查询的第 K 小值，直接返回就好了
	}
	}
	inline long long fstpow(long long n,long long m,long long md)// 快速幂，别傻到暴力求 x 次幂（
	{
	long long ans=1ll,base=n;base%=md;
	while(m)
	{
	if(m&1) ans*=base,ans%=md;
	base*=base,base%=md,m>>=1;
	}
	return ans;
	}
	long long query(long long l,long long r,long long x,long long y)
	{
	long long ans=0;
	set<A>::iterator it2=split(r+1),it1=split(l);// 依旧暴力拆区间
	// 对于每个集合，暴力求和
	for(set<A>::iterator it=it1;it!=it2;it++) ans+=fstpow(it->val,x,y)*(it->r-it->l+1),ans%=y;
	return ans;
	}
	signed main()
	{
	n=read(),m=read(),seed=read(),vmax=read();
	for(ri long long i=1;i<=n;i++) {awa[i]=myrand()%vmax+1;s.insert(A(i,i,awa[i]));}// 初始化每个集合
	s.insert(A(n+1,n+1,0));// 最后的一个小区间，防止访问越界
	for(ri long long i=1;i<=m;i++)
	{
	// 以下为生成数据
	long long x,y,opt=myrand()%4+1,l=myrand()%n+1,r=myrand()%n+1;
	// cout<<opt<<" "<<l<<" "<<r<<endl;
	if(l>r) swap(l,r);
	if(opt==3) x=myrand()%(r-l+1)+1;
	else x=myrand()%vmax+1;
	if(opt==4) y=(myrand()%vmax)+1;
	// 以上为生成数据
	if(opt==1) {add(l,r,x);continue;}// 区间加
	if(opt==2) {assign(l,r,x);continue;}// 区间改
	if(opt==3) {write(get_kth(l,r,x)),puts("");continue;}// 查找第 K 大
	if(opt==4) {write(query(l,r,x,y)),puts("");continue;}// 查询区间每个数 x 次方模 y 的和
	}
	return 0;// 没啦！
	}

下面给出一些注意事项

注意 $split$ 的时候最好要先 $split(r+1)$ 再 $split(l)$
注意 $split$ 返回的是包含当前分裂点的集合的指针
注意在初始化集合的时候在集合最后在加一个 $n+1$ 的值任意的集合，防止查找的时候越界

最后的时候说一下什么时候可以用珂朵莉树来做题

涉及到区间修改，区间赋值，区间查询并且数据随机的情况下使用

其中最重要的一点就是 区间赋值操作 和 数据随机

珂朵莉树的复杂度就是在这两个前提条件下保证的

没啦！这玩意调了好长时间都没调过，我先把博文放出来，等什么时候修好锅了再回来改

upd: 锅已修好，取模问题

ODT

# 珂朵莉树！

# 题目大意

# 下面给出 splitsplitsplit 代码

# 那么我们写一个对应的函数来实现这个操作，函数命名为 assignassignassign

# 接下来看区间加的操作

# 求区间第 KKK 小

# 最后一个操作，求区间每个数的 xxx 次幂模 yyy 的和

CF1899E Queue Sort

# 下面给出 $split$ 代码

# 那么我们写一个对应的函数来实现这个操作，函数命名为 $assign$

# 求区间第 $K$ 小

# 最后一个操作，求区间每个数的 $x$ 次幂模 $y$ 的和