珂朵莉树总结

第一次接触珂朵莉树是 $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)$。
珂朵莉树优秀的时间复杂度是建立在随机数据的基础上的。

white_tiger的博客

博客

评论

发表评论