珂朵莉树(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;
}
}
}
