RE+MLE 56pts求调

普通版已过，但这道题RE+MLE。

记录。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,m,ind,root,a,b,c,x; 
int last,ans;
struct node{
    int ls,rs,val,rnd,siz;
}tr[N];
void hbsiz(int x){
    int ls=tr[x].ls;
    int rs=tr[x].rs;
    tr[x].siz=tr[ls].siz+tr[rs].siz+1;
}
int nes(int val){
    tr[++ind].val=val;
    tr[ind].rnd=rand();
    tr[ind].siz=1;
    return ind;
}
void merge(int x,int y,int &a){
    if(!x || !y){a=x+y;return;}
    if(tr[x].rnd<tr[y].rnd){
        merge(tr[x].rs,y,tr[x].rs);
        a=x;hbsiz(x);
    }else{
        merge(x,tr[y].ls,tr[y].ls);
        a=y;hbsiz(y);
    }
}
void split_val(int x,int val,int &a,int &b){
    if(!x){a=b=0;return;}
    if(tr[x].val<=val){
        split_val(tr[x].rs,val,tr[x].rs,b);
        a=x;
    }else{
        split_val(tr[x].ls,val,a,tr[x].ls);
        b=x;
    }hbsiz(x);
}
int split_siz(int x,int pm){
    int ls=tr[x].ls;
    if(pm<=tr[ls].siz){
        return split_siz(ls,pm);
    }else if(pm==tr[ls].siz+1){
        return tr[x].val;
    }else{
        return split_siz(tr[x].rs,pm-tr[ls].siz-1);
    }
}
int main(){
//  freopen("P6136_1.in","r",stdin);
//  freopen("P6136_1.out","w",stdout);
    srand(time(0));
    cin >> n >> m;
//  cout << m << "\n";
    for(int i=1;i<=n;i++){
        cin >> x;
        split_val(root,x-1,a,b);
        merge(a,nes(x),a);
        merge(a,b,root);
    }
    int que,i=0;
    while(m--){
        cin >> que >> i;
        i=i^last;
        if(que==1){
            split_val(root,i-1,a,b);
            merge(a,nes(i),a);
            merge(a,b,root);
        }if(que==2){
            split_val(root,i-1,a,b);
            split_val(b,i,b,c);
            int ls=tr[b].ls,rs=tr[b].rs;
            merge(ls,rs,root);
            merge(a,root,root);
            merge(root,c,root);
        }if(que==3){
            split_val(root,i-1,a,b);
//          cout << tr[a].siz+1 << "\n";
            last=tr[a].siz+1;
            ans=ans^last;
            merge(a,b,root);

        }if(que==4){
//          cout << split_siz(root,i) << "\n";
            last=split_siz(root,i);
            ans^=last;
        }if(que==5){
            split_val(root,i-1,a,b);
//          cout << split_siz(a,tr[a].siz) << "\n";
            last=split_siz(a,tr[a].siz);
            ans^=last;
            merge(a,b,root);
        }if(que==6){
            split_val(root,i,a,b);
//          cout << split_siz(b,1) << "\n";
            last=split_siz(b,1);
            ans^=last;
            merge(a,b,root);
        }
    }cout << ans << "\n";
    return 0 ;
}