第一次接触珂朵莉树是 $2024.8.15$ 的那场考试,我当时就感觉我非常高兴,感觉很暴力。(然后那道题叫镜中的昆虫,意识到了自己的愚蠢。)
然后就趁热打铁写篇算法总结吧……
珂朵莉树,又称老司机树($Old\ Driver\ Tree,ODT$)。(所以珂朵莉=老司机?) 珂朵莉树本质上是一个很暴力的东西,主要维护的东西是各种操作搭配区间推平(实际上就是区间赋值)的序列。
那么珂朵莉树是如何实现上述操作的呢?
我们来看下面这个问题:
原题:$CF896C$。
给定一个序列,维护区间加、区间推平、求解区间第 $k$ 小、求解 $\bmod y$ 意义下区间各数 $x$ 次方和。保证数据非常随机。
感觉还是很难滴~因为这玩意不管是线段树、平衡树,还是莫队、分块,都似乎没有办法快速求解。
我们将相同的数看成一种颜色,就会发现,原序列形成了一个个颜色段,我们维护颜色段即可。
对于一次推平操作,我们将修改区间分割出来,全部变成推平形成的颜色即可。
而对于其他操作,则更加暴力:取出操作段,对于每个颜色块加值、对于所有颜色块暴力枚举 $k$ 小值、对于每个颜色块计算区间和就行了……
颜色段我们可以用 $set$ 维护。
乍看上去感觉时间复杂度直接爆炸,但是可以证明时间复杂度正确,为 $O(n\log n)$。
//中国珂学院 SNGXYZ 分院 OI 科第三办公室研究员 LYH
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,M=2e6+5;
int n,m,seed,vmax;
int qpow(int x,int y,int p){
int re=1;
while(y){
if(y&1) re=re*x%p;
x=x*x%p;y>>=1;
}return re;
}struct odt{
int l,r;
mutable int v;
bool operator<(const odt &c)const{
return l<c.l;
}
};set<odt>st;
#define iter set<odt>::iterator
struct chtholly{
iter spilt(int x){
iter it=st.lower_bound({x,0,0});
if(it!=st.end()&&(*it).l==x) return it;
it--;if((*it).r<x) return st.end();
int l=(*it).l,r=(*it).r,v=(*it).v;
st.erase(it);st.insert({l,x-1,v});
return st.insert({x,r,v}).first;
}void assign(int l,int r,int v){
iter tr=spilt(r+1),tl=spilt(l);
st.erase(tl,tr);st.insert({l,r,v});
}void add(int l,int r,int v){
iter tr=spilt(r+1),tl=spilt(l);
for(iter it=tl;it!=tr;it++) (*it).v+=v;
}int minn(int l,int r,int k){
priority_queue<pair<int,int> >q;
iter tr=spilt(r+1),tl=spilt(l);int sum=0;
for(iter it=tl;it!=tr;it++)
q.push({-(*it).v,(*it).r-(*it).l+1});
while(q.size()){
sum+=q.top().second;
if(sum>=k) return -q.top().first;
q.pop();
}
}int sum(int l,int r,int x,int y){
iter tr=spilt(r+1),tl=spilt(l);int re=0;
for(iter it=tl;it!=tr;it++)
re=(re+((*it).r-(*it).l+1)*qpow((*it).v%y,x,y)%y)%y;
return re%y;
}
}seniorious;
int rnd(){
int re=seed;
seed=(seed*7+13)%1000000007;
return re;
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>seed>>vmax;
for(int i=1;i<=n;i++)
st.insert({i,i,rnd()%vmax+1});int id=0;
while(m--){
int opt,l,r,x,y;
opt=rnd()%4+1;
l=rnd()%n+1;
r=rnd()%n+1;
if(l>r) swap(l,r);
if(opt==1){
x=rnd()%vmax+1;
seniorious.add(l,r,x);
}if(opt==2){
x=rnd()%vmax+1;
seniorious.assign(l,r,x);
}if(opt==3){
x=rnd()%(r-l+1)+1;
cout<<seniorious.minn(l,r,x)<<"\n";
}if(opt==4){
x=rnd()%vmax+1;y=rnd()%vmax+1;
cout<<seniorious.sum(l,r,x,y)<<"\n";
}
}return 0;
}/*
在太阳西斜的这个世界里,置身天上之森。
等这场战争结束之后,不归之人与望眼欲穿的众人。
人人本着正义之名,长存不灭的过去、逐渐消逝的未来。
我回来了,纵使日薄西山,即便看不到未来。
此时此刻的光辉,盼君勿忘。
————世界上最幸福的女孩
*/
有两个重点:
必须先 $spilt(r+1)$。
珂朵莉树优秀的时间复杂度是建立在随机数据的基础上的。