珂朵莉树
珂朵莉树（Old driver tree/老司机树/ODT）是一种由李欣隆发明的暴力数据结构，在随机数据下表现良好。珂朵莉树主要用于有大量区间推平操作的题目，但是在构造数据下表现十分不好。如果区间推平操作较多，则单一操作的时间复杂度为 \(O(\log_2n)\)。在特殊构造下，单一操作会退化成 \(O(n\log^2_2n)\)。
前置芝士
set 的应用。懂得 set 的迭代器用法。
做法
首先珂朵莉树的前提条件就是基于推平操作。也就是将 \([l,r]\) 全部修改成 \(x\)。所以最终整个序列会变成一个一个段，每个段的元素值均为 \(x\)。我们要做的就是维护这个东西。
所以我们首先要定义一个结构体，里面存 \(l,r,x\)。代表区间 \([l,r]\) 内的元素均为 \(x\)。注意，\(x\) 在实际定义时需要加上 mutable 前缀，只有这样我们才能够直接在之后定义的 set 里修改 \(x\)。
之后我们考虑怎么维护这个珂朵莉树。首先定义一个set来存这些区间，因为set 内部有排序功能所以区间是有连续性的，方便我们进行修改。
struct node{ ll l,r; mutable ll x; node(ll _l,ll _r=0,ll _x=true){ l=_l; r=_r; x=_x; } bool operator<(const node&K)const{ return l<K.l; }};setodt;然后我们考虑一个分离操作 \(f(x)\) 代表把一个区间范围包含了 \(x\) 的区间分成 \([l,x-1]\) 和 \([x,r]\)。这是因为实际操作时的询问不一定完全包含一个元素相同的区间，可能一个经过了修改还有一个是没有经过修改的，所以要分割。
auto split(ll x){ auto num=odt.lower_bound(node(x)); if(num!=odt.end()&&num->l==x){ return num;//如果 x 已经是一个区间的左端点了则直接返回这个区间。 } num--;//否则 x 一定被上一个区间包含（除了下面这种情况） if(num->rl,r=num->r; ll X=num->x; odt.erase(num); odt.insert(node(l,x-1,X)); return odt.insert(node(x,r,X)).first;//返回 [x,r] 的迭代器}之后是推平操作的实现。
void assign(ll l,ll r,bool work){ auto itr= split(r+1),itl= split(l);//注意这里要先分割 r+1，否则可能 re odt.erase(itl,itr);//删除原范围里面的所有段 odt.insert(node(l,r,work));//添加一个完整的新区间}之后所有的操作我们都做类似这样的处理：
void op(ll l,ll r,给定其他参数){ auto itr= split(r+1),itl= split(l); while(itl!=itr){ 暴力执行要求操作 itl++; }}这样子珂朵莉树就完成了。考虑到区间推平操作在随机数据下一定是范围大且数量算多的，所以这样的随机数据可以让set里面的元素数量不会很多。这样可以感性理解。具体的证明可以看这里。
例题CF915E Physical Education Lessons题目大意
对于一个长度为 \(n\) 且只含 \(0\) 或 \(1\) 的数组 \(a\)（初始全为 \(1\)），有 \(q\) 次操作，每次操作有两种：
- \(1,l,r\) 时将 \([l,r]\) 全部变为 \(0\)。
- \(2,l,r\) 时将 \([l,r]\) 全部变为 \(1\)。
对于每一个操作输出 \(a\) 还有几个 \(1\)。
\(1\leq n\leq 10^9,1\leq q\leq3\cdot 10^5\)
\(1\leq l,r\leq n\)
解法
首先因为本题只含有区间推平操作，所以可以使用珂朵莉树。
首先推平操作就是模版，具体对于几个 \(1\) 的维护可以在推平操作中直接枚举段落，然后如果此段的 \(x=1\)，则答案加上 \(r-l+1\) 即可。
代码
#include #include using namespace std;typedef long long ll;struct node {ll l,r;mutable bool work;node(ll _l,ll _r=0,bool _work=true) {l=_l;r=_r;work=_work;}bool operator<(const node&K)const {return l<K.l;}};setodt;auto split(ll x) {auto num=odt.lower_bound(node(x));if(num!=odt.end()&&num->l==x) {return num;}num--;if(num->rl,r=num->r;bool work=num->work;odt.erase(num);odt.insert(node(l,x-1,work));return odt.insert(node(x,r,work)).first;}ll ans=0;void assign(ll l,ll r,bool work) {auto itr= split(r+1),itl= split(l);auto it=itl;while(it!=itr) {if(it->work) {ans-=(it->r-it->l+1);}it++;}odt.erase(itl,itr);odt.insert(node(l,r,work));if(work) {ans+=r-l+1;}}int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);ll n,q;cin>>n;cin>>q;ans=n;odt.insert(node(1,n,true));while(q--) {ll l,r,k;cin>>l>>r>>k;assign(l,r,k!=1);cout<<ans<<"\n";}return 0;}CF896C Willem, Chtholly and Seniorious
这是珂朵莉树最开始的起源，但是具体做法也差不多一样。
题目大意
有一个长度为 \(n\) 的序列，请你写一种数据结构，共有 \(m\) 次操作，每一次操作你需要支持：
- \(1\) \(l\) \(r\) \(x\) ：将\([l,r]\) 区间所有数加上\(x\)
- \(2\) \(l\) \(r\) \(x\) ：将\([l,r]\) 区间所有数改成\(x\)
- \(3\) \(l\) \(r\) \(x\) ：输出将\([l,r]\) 区间从小到大排序后的第\(x\) 个数是的多少(即区间第\(x\) 小，数字大小相同算多次，保证 \(1\leq\) \(x\) \(\leq\) \(r-l+1\) )
- \(4\) \(l\) \(r\) \(x\) \(y\) ：输出\([l,r]\) 区间每个数字的\(x\) 次方的和模\(y\) 的值(即(\(\sum^r_{i=l}a_i^x\) ) \(\mod y\) )
保证数据随机生成
\(1\leq n,m\leq10^5,1\leq x,y\leq 10^9\)。
\(1\leq l,r\leq n\)
思路
对于第一种操作，我们直接枚举区间并加即可。
void op1(ll l,ll r,ll x) {auto itr= split(r+1),itl= split(l);while(itl!=itr) {itl->x+=x;itl++;}}第二种操作暴力推平即可。
第三种操作我们考虑把所有 \([l,r]\) 内的区间都存下来，然后排序并累计个数即可。
pairnum[MAXN];ll op3(ll l,ll r,ll x) {auto itr= split(r+1),itl= split(l);ll sz=0;while(itl!=itr) {num[++sz]= {itl->x,itl->r-itl->l+1};itl++;}sort(num+1,num+sz+1);ll v=0;while(x>0) {++v;x-=num[v].second;}return num[v].first;}第四种就快速幂直接乘跟加即可。但是注意快速幂的底数要取模，否则会溢出。
ll op4(ll l,ll r,ll x,ll y) {ll ans=0;auto itr= split(r+1),itl= split(l);while(itl!=itr) {ll val=ksm(itl->x,x,y);val=val*((itl->r-itl->l+1)%y);val%=y;ans=(ans+val)%y;itl++;}return ans;}代码
#include #include #include #define int long longusing namespace std;typedef long long ll;struct node {ll l,r;mutable ll x;node(ll _l,ll _r=0,ll _x=true) {l=_l;r=_r;x=_x;}bool operator<(const node&K)const {return l<K.l;}};setodt;auto split(ll x) {auto num=odt.lower_bound(node(x));if(num!=odt.end()&&num->l==x) {return num;}num--;if(num->rl,r=num->r;ll X=num->x;odt.erase(num);odt.insert(node(l,x-1,X));return odt.insert(node(x,r,X)).first;}void op2(ll l,ll r,ll X) {auto itr= split(r+1),itl= split(l);odt.erase(itl,itr);odt.insert(node(l,r,X));}void op1(ll l,ll r,ll x) {auto itr= split(r+1),itl= split(l);while(itl!=itr) {itl->x+=x;itl++;}}const ll MAXN=1e5+5;pairnum[MAXN];ll op3(ll l,ll r,ll x) {auto itr= split(r+1),itl= split(l);ll sz=0;while(itl!=itr) {num[++sz]= {itl->x,itl->r-itl->l+1};itl++;}sort(num+1,num+sz+1);ll v=0;while(x>0) {++v;x-=num[v].second;}return num[v].first;}ll ksm(ll a,ll b,ll k) {a%=k;ll ans=1;while(b) {if(b&1) {ans=(ans*a)%k;}a=(a*a)%k;b>>=1;}return ans%k;}ll op4(ll l,ll r,ll x,ll y) {ll ans=0;auto itr= split(r+1),itl= split(l);while(itl!=itr) {ll val=ksm(itl->x,x,y);val=val*((itl->r-itl->l+1)%y);val%=y;ans=(ans+val)%y;itl++;}return ans;}ll n,m,seed,vmax;ll rnd() {ll ret=seed;seed=(seed*7+13)%1000000007;return ret;}signed main() {ios::sync_with_stdio(false);cout.tie(0);cin>>n>>m>>seed>>vmax;for (int i=1;ir) {swap(l,r);}ll x;if (op == 3) {x = (rnd() % (r - l + 1)) + 1;} else {x = (rnd() % vmax) +1;}ll y=0;if (op == 4) {y = (rnd()%vmax) +1;}if(op==1) {op1(l,r,x);} else if(op==2) {op2(l,r,x);} else if(op==3) {cout<<op3(l,r,x)<<"\n";} else {cout<<op4(l,r,x,y)<<"\n";}}return 0;}