对于同一组数据每次输出可能是不一样的 P5055

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,bit=20;
struct treap{
    int l,r,val,siz,key,rev,sum;
    treap(){
        l=r=val=siz=key=rev=sum=0;
    }
}t[N*bit*2];
void pushup(int u){
    t[u].siz=t[t[u].l].siz+t[t[u].r].siz+1,t[u].sum=t[u].val+t[t[u].l].sum+t[t[u].r].sum;
}
mt19937 rnd(time(0));
int T,node,root[N],last;
int get(int val){
    t[++node].val=val,t[node].siz=1,t[node].key=rnd();
    return node;
}
void clone(int &u){
    t[++node]=t[u],u=node;
}
void pushdown(int u){
    if(t[u].rev){
        swap(t[u].l,t[u].r),t[t[u].l].rev^=1,t[t[u].r].rev^=1,t[u].rev=0;
    }
}
int merge(int x,int y){
    if(!x||!y){
        return x+y;
    }
    if(t[x].key>t[y].key){
        clone(x),pushdown(x),t[x].r=merge(t[x].r,y),pushup(x);
        return x;
    }
    clone(y),pushdown(y),t[y].l=merge(x,t[y].l),pushup(y);
    return y;
}
void split(int u,int len,int &x,int &y){
    if(!u){
        x=y=0;
    }
    else{
        clone(u),pushdown(u);
        if(t[t[u].l].siz<len){
            x=u,split(t[u].r,len-t[t[u].l].siz-1,t[u].r,y);
        }
        else{
            y=u,split(t[u].l,len,x,t[u].l);
        }
        pushup(u);
    }
}
void insert(int ver,int pos,int val){//把第ver个版本的pos后面插入val
    int x,y;
    split(root[ver],pos,x,y),root[ver]=merge(merge(x,get(val)),y);
}
void del(int ver,int val){//删除第val个数
    int x,y,z;
    split(root[ver],val,x,y),split(x,val-1,x,z),root[ver]=merge(x,y);
}
void rev(int ver,int l,int r){
    int x,y,z;
    split(root[ver],r,x,y),split(x,l-1,x,z),t[z].rev^=1,root[ver]=merge(merge(x,z),y);
}
int sum(int ver,int l,int r){
    int x,y,z,ret;
    split(root[ver],r,x,y),split(x,l-1,x,z),ret=t[z].sum,root[ver]=merge(merge(x,z),y);
    return ret;
}
signed main(){
    cin>>T;
    for(int typ,pre,l,r,i=1;i<=T;i++){
        cin>>pre>>typ>>l,root[i]=root[pre];
        if(typ==1){
            cin>>r,l^=last,r^=last,insert(i,l,r);
        }
        if(typ==2){
            l^=last,del(i,l);
        }
        if(typ==3){
            cin>>r,l^=last,r^=last,rev(i,l,r);
        }
        if(typ==4){
            cin>>r,l^=last,r^=last,last=sum(i,l,r);
            cout<<last<<'\n';
        }
    }   
}