珂朵莉树(ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构,因那道题题面(CF896C)关于珂朵莉而得名。
珂朵莉树适用于以下的情况:维护一个序列,有区间赋值操作,数据随机。下面是珂朵莉树板子题:
维护一个序列,需要支持以下操作
1. 将 $[l,r]$ 区间所有数加上 x
2. 将 $[l,r]$ 区间所有数改成 x
3. 求 $[l,r]$ 区间第 k 小
4. 求 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值 (即 $\left(\sum_{i=l}^{r} a_{i}^{x}\right) \bmod y)$
– CF896C Willem, Chtholly and Seniorious
支持的操作还可以有很多,只要暴力能做珂朵莉树一般都可以做。
珂朵莉树的思想是维护一堆区间,合并相同值的区间,这样区间总数就可以减少。
珂朵莉树非常依赖区间赋值操作,如果区间赋值操作很少或者区间赋值的区间都较短,那么珂朵莉树和暴力就没什么区别了。
显然,要卡珂朵莉树非常容易。但对于数据完全随机的情况,珂朵莉树就可以跑得飞快。有很多题可以用珂朵莉树水过,甚至比正解还快。
思路
珂朵莉树维护了很多区间。
一个区间表示一段相同的数。一个区间$(l,r,num)$表示从左端点 $l$ 到右端点 $r$,中间的数字全部为 $num$。
例如 $1,2,3,3,3,4,4,5$ 可以用 $5$ 个区间来表示:$(1,1,1)(2,2,2)(3,5,3)(6,7,4)(8,8,5)$。
区间赋值的时候,我们可以删去一些区间并用一个大区间代替它们,区间数量就少了很多。
而查询只需要找出相应的区间,然后暴力统计即可。
如果某次操作的边界在某个区间的中心,那么将这个区间断开即可。
我们用 set 维护区间左端点位置的值,使区间始终保持有序。
区间结构体定义
struct node{ long long l,r; //左端点,右端点 mutable long long num; //区间值 bool operator<(const node y) const{ return l<y.l; } };
Split
Split 操作用来将一个区间断开。
set<node>::iterator split(long long x){ //返回位置为 x 的区间迭代器,如果不存在该区间则 split 该位置所在的区间成两份 node tmp={x}; set<node>::iterator it=s.lower_bound(tmp); //查找所在的位置 if (it!=s.end()&&it->l==x){ //如果区间边界就是 x return it; //那么直接返回该区间 } it--; //否则退回前一个区间 long long l=it->l,r=it->r,num=it->num; s.erase(it); //移除这个区间 tmp={l,x-1,num}; s.insert(tmp); //插入 split 后的左半区间 tmp={x,r,num}; return s.insert(tmp).first; //插入 split 后的右半区间并返回该区间的迭代器 //insert 方法返回的是一个 pair,pair 的第一个元素即为插入后元素的迭代器 }
区间赋值操作 (Assign)
删除该区间所覆盖的所有小区间,并插入一个大区间来代替它们。
void assign(long long l,long long r,long long x){ //将 l 到 r 的数赋值为 x set<node>::iterator R=split(r+1); //找右边端点区间 (注意这里要先找 R,否则如果为边界情况区间会被 erase 一次,接下来的 erase 操作就会错误) set<node>::iterator L=split(l); //找左边端点区间 s.erase(L,R); //移除左右端点区间之间的这些区间 node tmp={l,r,x}; s.insert(tmp); //插入新的大区间 }
查询操作
就是暴力,找出相应区间并暴力统计
区间和
long long query_sum(long long l,long long r){ //l 到 r 的区间和 set<node>::iterator L=split(l),R=split(r+1); //找左右端点区间 long long ans=0; while (L!=R){ ans+=L->num*(L->r-L->l+1); //遍历求和 ans%=y; L++; } return ans; }
区间 x 次方和
和求和一样,只是改成快速幂
long long query_pow_sum(long long l,long long r,long long x,long long y){ //l 到 r 的 x 次方和模 y set<node>::iterator L=split(l),R=split(r+1); long long ans=0; while (L!=R){ ans+=qpow(L->num,x,y)*(L->r-L->l+1); //快速幂并累计 ans%=y; L++; } return ans; }
区间第 k 小
取出相应区间内的所有区间排序,从前到后找第 k 小
long long query_kth(long long l,long long r,long long k){ //l 到 r 区间内第 k 小的数 set<node>::iterator L=split(l),R=split(r+1); vector<pair<long long,long long> > t; while (L!=R){ t.push_back(make_pair(L->num,L->r-L->l+1)); //插入 vector L++; } sort(t.begin(),t.end()); //排序 for (long long i=0;i<t.size();i++){ k-=t[i].second; if (k<=0){ return t[i].first; //达到前 k 个就返回 } } return -2147483647; }
其他操作
你应该已经发现了,珂朵莉树其实就是暴力,暴力怎么写珂朵莉树就怎么写,真·暴力数据结构
例题代码
CF896C Willem, Chtholly and Seniorious
#include<bits/stdc++.h> using namespace std; long long n,m,seed,vmax; long long rnd(){ long long ret=seed; seed=(seed*7+13)%1000000007; return ret; } inline long long qpow(long long a,long long b,long long p){ long long ans=1; a%=p; while(b){ if(b&1){ ans=ans*a%p; } a=a*a%p; b>>=1; } return ans; } struct node{ long long l,r; mutable long long num; bool operator<(const node y) const{ return l<y.l; } }; set<node> s; set<node>::iterator split(long long x){ node tmp={x}; set<node>::iterator it=s.lower_bound(tmp); if (it!=s.end()&&it->l==x){ return it; } it--; long long l=it->l,r=it->r,num=it->num; s.erase(it); tmp={l,x-1,num}; s.insert(tmp); tmp={x,r,num}; return s.insert(tmp).first; } void assign(long long l,long long r,long long x){ set<node>::iterator R=split(r+1); set<node>::iterator L=split(l); s.erase(L,R); node tmp={l,r,x}; s.insert(tmp); } long long query_kth(long long l,long long r,long long k){ set<node>::iterator L=split(l),R=split(r+1); vector<pair<long long,long long> > t; while (L!=R){ t.push_back(make_pair(L->num,L->r-L->l+1)); L++; } sort(t.begin(),t.end()); for (long long i=0;i<t.size();i++){ k-=t[i].second; if (k<=0){ return t[i].first; } } return -2147483647; } long long query_pow_sum(long long l,long long r,long long x,long long y){ set<node>::iterator L=split(l),R=split(r+1); long long ans=0; while (L!=R){ ans+=qpow(L->num,x,y)*(L->r-L->l+1); ans%=y; L++; } return ans; } void add(long long l,long long r,long long x){ set<node>::iterator L=split(l),R=split(r+1); while (L!=R){ L->num+=x; L++; } } int main(){ cin>>n>>m>>seed>>vmax; for (long long i=1;i<=n;i++){ node tmp={i,i,rnd()%vmax+1}; s.insert(tmp); } for (long long i=1;i<=m;i++){ long long op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y; if (l>r){ swap(l,r); } if (op==3){ x=(rnd()%(r-l+1))+1; }else{ x=(rnd()%vmax)+1; } if (op==4){ y=(rnd()%vmax)+1; } if (op==1){ add(l,r,x); } if (op==2){ assign(l,r,x); } if (op==3){ cout<<query_kth(l,r,x)<<endl; } if (op==4){ cout<<query_pow_sum(l,r,x,y)<<endl; } } }