前言

珂朵莉树Old Driver Tree (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 R=split(r+1),L=split(l); //找左右端点区间
	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 R=split(r+1),L=split(l);
	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 R=split(r+1),L=split(l);
	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 R=split(r+1),L=split(l);
	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 R=split(r+1),L=split(l);
	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 R=split(r+1),L=split(l);
	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;
		}
	}
}