MLE是神马情况

MLE on #4

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,opt,us,spa,splx,sply,splz,root,las,cr;
struct node {
    int son[2],siz,val,key;
} q[1000009];
void upd(int x) {q[x].siz=q[q[x].son[0]].siz+q[q[x].son[1]].siz+1;}
int new_root(int value) {++n,q[n].siz=1,q[n].val=value,q[n].key=rand();return n;}
int merge(int x,int y) { //x < y 
    if(!x||!y) return x+y;
    if(q[x].key<q[y].key) {
        q[x].son[1]=merge(q[x].son[1],y),upd(x);
        return x;
    }
    else {
        q[y].son[0]=merge(x,q[y].son[0]),upd(y);
        return y;
    }
}
void split(int now,int k,int &x,int &y) {
    if(!now) x=y=0;
    else {
        if(q[now].val<=k) x=now,split(q[now].son[1],k,q[now].son[1],y);
        else y=now,split(q[now].son[0],k,x,q[now].son[0]);
        upd(now);
    }
} 
int kth(int now,int k) {
    while(1) {
        if(k<=q[q[now].son[0]].siz) now=q[now].son[0];
        else if(k==q[q[now].son[0]].siz+1) return q[now].val;
        else k-=q[q[now].son[0]].siz+1,now=q[now].son[1];
    }
}
signed main() {
    srand(1919810);
    scanf("%d%d",&us,&m);
    while(us--) scanf("%d",&cr),split(root,cr,splx,sply),root=merge(merge(splx,new_root(cr)),sply),cr=0;
    while(m--) {
        scanf("%d%d",&opt,&us),us^=las;
        if(opt==1) split(root,us,splx,sply),root=merge(merge(splx,new_root(us)),sply);
        if(opt==2) split(root,us,splx,sply),split(splx,us-1,splx,splz),splz=merge(q[splz].son[0],q[splz].son[1]),root=merge(merge(splx,splz),sply);
        if(opt==3) split(root,us-1,splx,sply),las=q[splx].siz+1,root=merge(splx,sply),cr^=las;
        if(opt==4) las=kth(root,us),cr^=las;
        if(opt==5) split(root,us-1,splx,sply),las=kth(splx,q[splx].siz),root=merge(splx,sply),cr^=las;
        if(opt==6) split(root,us,splx,sply),las=kth(sply,1),root=merge(splx,sply),cr^=las;
    }
    printf("%d\n",cr);
    return 0;
}