题解 P5055 【【模板】可持久化文艺平衡树】

· · 题解

skip2004秒出的一种不用下放标记的写法

可持久化区间翻转，考虑可持久化Treap实现。

1,2,4操作都好实现，4操作维护一下子树和即可。

关键就在那个区间翻转操作上。

传统的区间翻转，都是要打一个翻转标记，然后下放。但如果可持久化的话，就有点难处理。

如果我们能事先知道翻转后的区间，那就方便很多了。

维护一个反序列的Treap，则要翻转的区间在反Treap中的对应区间，就是翻转后的序列。

然后，翻转一段区间，就直接在正、反两个Treap中，把对应区间split出来，然后互换即可。

时间复杂度是O(n\log n)的。常数会比较大（维护两个Treap，至少2倍）。

空间会用得比较多。把rand数组用unsigned short压一压会比较好。

Code：

#include<cstdio>
#include<cctype>
#define N 200005
#define P 100
#define LL long long
#define next_int(x)(x^=x<<13,x^=x>>17,x^=x<<5)
int seed=19260817;
inline LL readint(){
    int c=getchar(),b=0;
    LL d=0;
    for(;!isdigit(c);c=getchar())b=c=='-';
    for(;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^'0');
    return b?-d:d;
}
int L[N*P],R[N*P],sz[N*P],s[N*P];
LL sm[N*P];
unsigned short rnd[N*P];
int cnt=0,rt[N],irt[N];
LL ans=0;
#define update(x)(sm[x]=sm[L[x]]+sm[R[x]]+s[x],sz[x]=sz[L[x]]+sz[R[x]]+1)
int merge(int x,int y){
    if(!x||!y)return x|y;
    int u=++cnt;
    if(rnd[x]<rnd[y]){
        rnd[u]=rnd[x];
        L[u]=L[x];
        s[u]=s[x];
        sm[u]=sm[x];
        sz[u]=sz[x];
        R[u]=merge(R[x],y);
    }else{
        rnd[u]=rnd[y];
        s[u]=s[y];
        R[u]=R[y];
        sm[u]=sm[y];
        sz[u]=sz[y];
        L[u]=merge(x,L[y]);
    }
    update(u);
    return u;
}
void split(int u,int k,int&x,int&y){
    if(!u)x=y=0;else
    if(k==0)x=0,y=u;else
    if(k==sz[u])x=u,y=0;else
    if(sz[L[u]]>=k){
        y=++cnt;
        rnd[y]=rnd[u];
        R[y]=R[u];
        s[y]=s[u];
        sm[y]=sm[u];
        sz[y]=sz[u];
        split(L[u],k,x,L[y]);
        update(y);
    }else{
        x=++cnt;
        rnd[x]=rnd[u];
        L[x]=L[u];
        s[x]=s[u];
        sm[x]=sm[u];
        sz[x]=sz[u];
        split(R[u],k-sz[L[u]]-1,R[x],y);
        update(x);
    }
}
void insert(int p,int f,int ver,int t){
    int len=sz[rt[ver]],x,y;
    split(rt[ver],p,x,y);
    int nw=++cnt;
    s[nw]=f,rnd[nw]=next_int(seed)&65535;sm[nw]=f;sz[nw]=1;
    rt[t]=merge(merge(x,cnt),y);
    split(irt[ver],len-p,x,y);
    s[++cnt]=f,rnd[cnt]=rnd[nw];sm[cnt]=f;sz[cnt]=1;
    irt[t]=merge(merge(x,cnt),y);
}
void erase(int p,int ver,int t){
    int len=sz[rt[ver]],a,b,c,d;
    split(rt[ver],p,a,b);
    split(a,p-1,c,d);
    rt[t]=merge(c,b);
    split(irt[ver],len-p+1,a,b);
    split(a,len-p,c,d);
    irt[t]=merge(c,b);
}
void reverse(int ver,int l,int r,int t){
    int len=sz[rt[ver]];
    int r1,r2,r3,r0,i1,i2,i3,i0;
    split(rt[ver],r,r0,r3);
    split(r0,l-1,r1,r2);
    split(irt[ver],len-l+1,i0,i3);
    split(i0,len-r,i1,i2);
    rt[t]=merge(merge(r1,i2),r3);
    irt[t]=merge(merge(i1,r2),i3);
}
LL query(int ver,int l,int r,int t){
    rt[t]=rt[ver],irt[t]=irt[ver];
    int _0,_1,_2,_3;
    split(rt[ver],r,_0,_3);
    split(_0,l-1,_1,_2);
    return sm[_2];
}
int main(){
    for(int T=readint(),t=1;t<=T;++t){
        int v=readint(),opt=readint();
        switch(opt){
            case 1:{
                int p=readint()^ans,x=readint()^ans;
                insert(p,x,v,t);
                break;
            }
            case 2:{
                int p=readint()^ans;
                erase(p,v,t);
                break;
            }
            case 3:{
                int l=readint()^ans,r=readint()^ans;
                reverse(v,l,r,t);
                break;
            }
            case 4:{
                int l=readint()^ans,r=readint()^ans;
                printf("%lld\n",ans=query(v,l,r,t));
                break;
            }
        }
    }
    return 0;
}