忘掉文艺平衡树怎么写怎么办 | 珂朵莉树Pro Max

NotMonika · 2026-08-01 07:10:58 · 算法·理论

声明：以下所有复杂度 n,m 不分。

好，假设你忘掉了关于文艺平衡树怎么写。（也有可能你本来就不会）
你的面前摆着这么一道题：

给出一个序列，区间加，区间和，区间复制，区间翻转，区间推平。保证数据随机。

你忘掉了平衡树怎么写，自然也想不到怎么去用可持久化引用计数文艺平衡树去做这道题。
好在你曾经~被名称骗进去~学了珂朵莉树。
::::info[关于珂朵莉树的名称] 其发明者 lxl 曾经认为这个算法应该叫做颜色段均摊，但是由于珂朵莉树是社区主流叫法，~并且珂朵莉很可爱~，所以本文中统一称为珂朵莉树。 :::: 所以你就一眼秒了这题[^1]。

可出题人不会那么善良，所以他不再保证数据随机了。
怎么办？难道你就要向可持久化引用计数文艺平衡树投降了？
你决定只维护原数组的映射，并像普通珂朵莉树一样操作时做区间分裂。
具体的，设珂朵莉树中每个节点对应一个区间：

• 区间赋值：直接当普通珂朵莉树做就可以了。
• 区间加区间和：维护原数组的前缀和和当前区间的变化量，区间和直接求前缀和和变化量的和就可以了。
• 区间翻转：再打一个标记，直接把对应的那些区间取出来然后打上翻转标记就可以了。
• 区间交换和区间复制：暴力把对应区间取出来然后乱搞。

然后你会发现你的代码可以在 O\left(n\right) 的时间内被卡到 O\left(n\right) 个块。
所以你每有 O\left(\sqrt{n}\right) 个块就把原来的操作计算一下贡献然后建立新的数组。后面的操作就把计算完贡献的数组作为原数组，重复上面的过程就可以了。
不难发现其总复杂度是 O\left(n\sqrt{n}\right) 的。 ::::warning[除了区间复制]{open} 理论上每次复制可以让块数倍增，可以把复杂度卡到 O\left(\frac{n^2}{\log{n}}\right)。不过这道题没卡。希望以后也不要卡。 :::info[但是？]{open} 好像可以随机重构防止被卡。 ::: :::: 然后你发现调几下重构阈值就跑到最优解了。
::::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5,B=1000,P=1e9+7;
int n,m,a[N],b[N],s[N],last;
struct node{
    int l,r,dlt,fil,rev;
    int size(){return r-l+1;}
    int sum(){
        if(fil!=-1)return (fil+dlt)*size();
        return s[r]-s[l-1]+dlt*size();
    }
};
vector<node>odt;
void rebuild(){
    if(odt.size()<B)
        return;
    int p=0;
    for(node&nd:odt)
        if(nd.fil!=-1){
            for(int i=1;i<=nd.size();i++)b[++p]=nd.fil+nd.dlt;
        }else {
            if(nd.rev)for(int i=nd.r;i>=nd.l;i--)b[++p]=a[i]+nd.dlt;
            else for(int i=nd.l;i<=nd.r;i++)b[++p]=a[i]+nd.dlt;
        }

    for(int i=1;i<=n;i++)a[i]=b[i],s[i]=s[i-1]+a[i];
    odt.clear(),odt.push_back({1,n,0,-1,0});
}
int split(int x){
    if(x==0)return 0;
    for(int i=0;i<odt.size();i++){
        if(odt[i].size()==x)return i+1;
        else if(odt[i].size()<x)x-=odt[i].size();
        else{
            if(odt[i].rev){
                odt.insert(odt.begin()+i+1,{odt[i].l,odt[i].r-x,odt[i].dlt,odt[i].fil,1});
                odt[i].l=odt[i].r-x+1;
            }else{
                odt.insert(odt.begin()+i+1,{odt[i].l+x,odt[i].r,odt[i].dlt,odt[i].fil,0});
                odt[i].r=odt[i].l+x-1;
            }
            return i+1;
        }
    }
    return odt.size();
}
void add(int l,int r,int v){
    int nl=split(l-1),nr=split(r);
    for(int i=nl;i<nr;i++)odt[i].dlt+=v;
    rebuild();
}
int sum(int l,int r){
    int nl=split(l-1),nr=split(r),ans=0;
    for(int i=nl;i<nr;i++)ans+=odt[i].sum();
    rebuild();
    return ans;
}
void assign(int l,int r,int v){
    int nl=split(l-1),nr=split(r);
    odt.erase(odt.begin()+nl,odt.begin()+nr);
    odt.insert(odt.begin()+nl,{l,r,0,v,0});
    rebuild();
}
void cpy(int l1,int r1,int l2,int r2){
    int nl2=split(l2-1),nr2=split(r2);
    vector<node>tmp(odt.begin()+nl2,odt.begin()+nr2);
    int nl1=split(l1-1),nr1=split(r1);
    odt.erase(odt.begin()+nl1,odt.begin()+nr1);
    odt.insert(odt.begin()+nl1,tmp.begin(),tmp.end());
    rebuild();
}
void swp(int l1,int r1,int l2,int r2){
    int nl1=split(l1-1),nr1=split(r1);
    vector<node>tmp1(odt.begin()+nl1,odt.begin()+nr1);
    int nl2=split(l2-1),nr2=split(r2);
    vector<node>tmp2(odt.begin()+nl2,odt.begin()+nr2);
    nl1=split(l1-1),nr1=split(r1);
    odt.erase(odt.begin()+nl1,odt.begin()+nr1);
    odt.insert(odt.begin()+nl1,tmp2.begin(),tmp2.end());
    nl2=split(l2-1),nr2=split(r2);
    odt.erase(odt.begin()+nl2,odt.begin()+nr2);
    odt.insert(odt.begin()+nl2,tmp1.begin(),tmp1.end());
    rebuild();
}
void rev(int l,int r){
    int nl=split(l-1),nr=split(r);
    for(int i=nl;i<nr;i++)odt[i].rev^=1;
    reverse(odt.begin()+nl,odt.begin()+nr);
    rebuild();
}
int op,l,r,x,y;
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> a[i],s[i]=s[i-1]+a[i];
    odt.push_back({1,n,0,-1,0});
    while(m--){
        cin >> op >> l >> r;
        l^=last,r^=last;
        if(op==1)cout << (last=sum(l,r)%P) << '\n';
        else if(op==2)cin >> x,x^=last,assign(l,r,x);
        else if(op==3)cin >> x,x^=last,add(l,r,x);
        else if(op==4)cin >> x >> y,x^=last,y^=last,cpy(x,y,l,r);
        else if(op==5)cin >> x >> y,x^=last,y^=last,swp(l,r,x,y);
        else rev(l,r);
    }
    for(node&nd:odt)
        if(nd.fil!=-1){
            for(int i=1;i<=nd.size();i++)cout << (nd.fil+nd.dlt)%P << ' ';
        }else {
            if(nd.rev)for(int i=nd.r;i>=nd.l;i--)cout << (a[i]+nd.dlt)%P << ' ';
            else for(int i=nd.l;i<=nd.r;i++)cout << (a[i]+nd.dlt)%P << ' ';
        }
}

::::

然后你又遇到了一道题。

给出一个序列，区间加，区间翻转，区间循环向右移，插入删除，区间最小值。

你发现区间最小值不能 O\left(n\right) - O\left(1\right) 维护。
直接用线段树做是 O\left(n\sqrt{n\log{n}}\right) 的。
但你发现可以只在区间分裂的时候求最小值，甚至不用写线段树，只需要拿分块就可以直接做到 O\left(n\sqrt{n}\right) 的复杂度[^2]。
然后就做完了。
::::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,B=N+1,L=400;
int a[N],n,m;
namespace blockmin{
    int w[N/B+1];
    void build(){
        fill(w,w+n/B+1,INT_MAX);
        for(int i=1;i<=n;i++)w[i/B]=min(w[i/B],a[i]);
    }
    int query(int l,int r){
        int ans=INT_MAX;
        if(l/B==r/B){
            for(int i=l;i<=r;i++)ans=min(ans,a[i]);
            return ans;
        }
        for(;l%B&&l<=n;l++)ans=min(ans,a[l]);
        for(;(r+1)%B&&r>=1;r--)ans=min(ans,a[r]);
        for(int i=l/B;i<=r/B;i++)ans=min(ans,w[i]);
        return ans;
    }
}
namespace chtholly{
    int b[N];
    struct node{
        int l,r,rev,dlt,minv,fil,filt;
        int size(){return r-l+1;}
        int min(){return (filt?fil:minv)+dlt;}
    };
    vector<node>odt;
    void init(){
        odt.clear(),blockmin::build(),odt.push_back({1,n,0,0,blockmin::query(1,n),0,0});
    }
    void rebuild(){
        if(odt.size()<L)return;
        int p=0;
        for(node&nd:odt)
            if(nd.filt)for(int i=1;i<=nd.size();i++)b[++p]=nd.fil+nd.dlt;
        else if(nd.rev)for(int i=nd.r;i>=nd.l;i--)b[++p]=a[i]+nd.dlt;
        else for(int i=nd.l;i<=nd.r;i++)b[++p]=a[i]+nd.dlt;
        for(int i=1;i<=p;i++)a[i]=b[i];
        n=p,init();
    }
    int split(int x){
        if(!x)return 0;
        for(int p=0;p<odt.size();p++){
            if(x>odt[p].size())x-=odt[p].size();
            else if(x==odt[p].size())return p+1; 
            else{
                if(odt[p].rev)odt.insert(odt.begin()+p+1,{odt[p].l,odt[p].r-x,odt[p].rev,odt[p].dlt,blockmin::query(odt[p].l,odt[p].r-x),odt[p].fil,odt[p].filt}),odt[p].l=odt[p].r-x+1;
                else odt.insert(odt.begin()+p+1,{odt[p].l+x,odt[p].r,odt[p].rev,odt[p].dlt,blockmin::query(odt[p].l+x,odt[p].r),odt[p].fil,odt[p].filt}),odt[p].r=odt[p].l+x-1;
                return odt[p].minv=blockmin::query(odt[p].l,odt[p].r),p+1;
            }
        }
        return odt.size();
    }
    void add(int l,int r,int v){
        int nl=split(l-1),nr=split(r);
        for(int i=nl;i<nr;i++)odt[i].dlt+=v;
        rebuild();
    }
    void rev(int l,int r){
        int nl=split(l-1),nr=split(r);
        reverse(odt.begin()+nl,odt.begin()+nr);
        for(int i=nl;i<nr;i++)odt[i].rev^=1;
        rebuild();
    }
    void revo(int l,int r,int t){
        if(t<=0)return;
        int nl=split(l-1),nm=split(r-t),nr=split(r);
        rotate(odt.begin()+nl,odt.begin()+nm,odt.begin()+nr);
        rebuild();
    }
    void del(int p){
        int nl=split(p-1),nr=split(p);
        odt.erase(odt.begin()+nl,odt.begin()+nr),rebuild();
    }
    void insert(int p,int v){odt.insert(odt.begin()+split(p),{1,1,0,0,v,v,1}),rebuild();}
    int min(int l,int r){
        int nl=split(l-1),nr=split(r),ans=INT_MAX;
        for(int i=nl;i<nr;i++)ans=std::min(odt[i].min(),ans);
        return rebuild(),ans;
    }
}
string op;
int x,y,z;
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    cin >> m,chtholly::init();
    while(m--){
        cin >> op;
        if(op=="ADD")cin >> x >> y >> z,chtholly::add(x,y,z);
        else if(op=="REVERSE")cin >> x >> y,chtholly::rev(x,y);
        else if(op=="REVOLVE")cin >> x >> y >> z,chtholly::revo(x,y,z%(y-x+1));
        else if(op=="INSERT")cin >> x >> y,chtholly::insert(x,y);
        else if(op=="DELETE")cin >> x,chtholly::del(x);
        else if(op=="MIN")cin >> x >> y,cout << chtholly::min(x,y) << '\n';
    }
    return 0;
}

::::

参考阅读：

• ODT 的映射思想的推广
• 我写的 P5586 的题解

[^1]:但是我写的时候普通珂朵莉树交了 998244353 发也没有通过。 [^2]:块长取 N+1 直接跑到最优解了，令人忍俊不禁。