【HDU 6087】—Rikka with Sequence（可持久化平衡树）

可持久化平衡树
第三个操作只需要记录一个最开始版本的根就可以了
第二个操作实际上是把 $[l-k,l-1]$ 复制多次
可以倍增复制
由于卡空间，定期重构平衡树
我写的非旋 $treap$
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int M=1e6+5;
inline int rnd(){
    return rand()<<15|rand();
}
int a[M];
namespace treap{
    char x;
    int stk[M],e[M],top,ecnt;
    int rt,root,tot;
    int son[M][2],siz[M],val[M];
    ll s[M];
    int vis[M],tim;
    char y;
    #define lc(u) son[u][0]
    #define rc(u) son[u][1]
    inline int newnode(int v=0){
        int u;
        if(top)u=stk[top--];
        else u=++tot;
        e[++ecnt]=u;
        val[u]=v,lc(u)=rc(u)=0,s[u]=v,siz[u]=1;
        return u;
    }
    inline void copy(int u,int r1){
        lc(u)=lc(r1),rc(u)=rc(r1),val[u]=val[r1],siz[u]=siz[r1],s[u]=s[r1];
    }
    inline void pushup(int u){
        siz[u]=siz[lc(u)]+siz[rc(u)]+1;
        s[u]=s[lc(u)]+s[rc(u)]+val[u];
    }
    inline void split(int u,int &r1,int &r2,int k){
        if(!u){r1=r2=0;return;}
        if(siz[lc(u)]>=k){
            r2=newnode(),copy(r2,u);
            split(lc(u),r1,lc(r2),k);
            pushup(r2);
        }
        else{
            r1=newnode(),copy(r1,u);
            split(rc(u),rc(r1),r2,k-siz[lc(u)]-1);
            pushup(r1);
        }
    }
    inline void merge(int &u,int r1,int r2){
        if(!r1||!r2){u=r1+r2;return;}
        if(rnd()%(siz[r1]+siz[r2])<siz[r1]){
            u=newnode(),copy(u,r1);
            merge(rc(u),rc(r1),r2);
        }
        else{
            u=newnode(),copy(u,r2);
            merge(lc(u),r1,lc(r2));
        }
        pushup(u);
    }
    inline ll query(int l,int r){
        int r1,r2,r3;
        split(rt,r1,r3,r);
        split(r1,r1,r2,l-1);
        ll res=s[r2];
        merge(r1,r1,r2);
        merge(rt,r1,r3);
        return res;
    }
    inline void update(int l,int r,int k){
        int r1,r2,r3,r4,r5,r6;
        split(rt,r1,r4,r);
        split(r1,r1,r3,l-1);
        split(r1,r1,r2,l-k-1);
        r5=r2,r3=0;
        int b=(r-l+1)/k+1;
        for(;b;b>>=1,merge(r5,r5,r5))if(b&1)merge(r3,r3,r5);
        split(r3,r3,r6,r-l+1);
        merge(r1,r1,r2),merge(r1,r1,r3);
        merge(rt,r1,r4);
    }
    inline void change(int l,int r){
        int r1,r2,r3,r4,r5,r6;
        split(root,r1,r3,r);
        split(r1,r1,r2,l-1);
        split(rt,r4,r6,r);
        split(rt,r4,r5,l-1);
        merge(r4,r4,r2);
        merge(rt,r4,r6);
    }
    inline void insert(int k){
        int r1=newnode(k);
        merge(rt,rt,r1);
    }
    void dfs(int u){
        if(!u)return;
        vis[u]=tim;
        dfs(lc(u)),dfs(rc(u));
    }
    inline void rebuild(){
        tim++,dfs(root),dfs(rt);int cnt=0;
        for(int i=1;i<=ecnt;i++)if(vis[e[i]]!=tim)stk[++top]=e[i];else e[++cnt]=e[i];
        ecnt=cnt;
    }
    void build(int &u,int l,int r){
        if(l>r){u=0;return;}
        int mid=(l+r)>>1;
        u=newnode(a[mid]);
        if(l==r)return;
        build(lc(u),l,mid-1),build(rc(u),mid+1,r);
        pushup(u);
    }
}
int n,m;
int main(){
    srand(time(NULL));
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    treap::build(treap::rt,1,n);
    treap::root=treap::rt;
    while(m--){
        int op=read(),l=read(),r=read();
        if(op==1){
            cout<<treap::query(l,r)<<'
';
        }
        else if(op==2){
            int k=read();
            treap::update(l,r,k);
        }
        else {
            treap::change(l,r);
        }
        if(treap::ecnt>=900000)treap::rebuild();
    }
}