fhq treap TLE+WA求助

直接把过了原版的代码改了，40pts，TLE+WA

#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include<cstdlib>
#include <algorithm>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,opt,k,rt,tot,x,y,z,las,ans,maxn;
struct node {
    int ch[2];
    int key;
    int val;
    int size;
}tr[N+M];
int read() {
    int u=0,f=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(ch>='0'&&ch<='9') u=(u<<3)+(u<<1)+(ch^48),ch=getchar();
    return u*f;
}
int new_node (int k) {
    tr[++tot].key=k;
    tr[tot].val=rand();
    tr[tot].size=1;
    return tot;
}
void maintain(int t) {
    tr[t].size=tr[tr[t].ch[0]].size+tr[tr[t].ch[1]].size+1;
}
void split(int p,int k,int &x,int &y) { 
    if(!p) {
        x=y=0;
        return;
    }
    if(tr[p].key<=k) { 
        x=p;         
        split(tr[p].ch[1],k,tr[p].ch[1],y);
    }
    else {
        y=p;
        split(tr[p].ch[0],k,x,tr[p].ch[0]);
    }
    maintain(p);
}
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(tr[x].val<tr[y].val) {         
        tr[x].ch[1]=merge(tr[x].ch[1],y);
        maintain(x);       
        return x;
    }
    else {
        tr[y].ch[0]=merge(x,tr[y].ch[0]); 
        maintain(y);
        return y;
    }

}
int val_by_rank(int p,int k) {
    while(1) {
        if(tr[tr[p].ch[0]].size>=k) {
            p=tr[p].ch[0];
        }
        else {
            k=k-tr[tr[p].ch[0]].size-1;
            if(k<=0) return tr[p].key;
            p=tr[p].ch[1];
        }
    }
}
int main() {
    srand(time(0));
    n=read();m=read();
    for(int i=1;i<=n;i++) k=read(),rt=merge(rt,new_node(k));
    for(int i=1;i<=m;i++) {
        opt=read();k=read();
        k^=las;
        if(opt==1) {
            split(rt,k,x,y);     
            rt=merge(merge(x,new_node(k)),y);
        }
        else if(opt==2) {
            split(rt,k,x,z);
            split(x,k-1,x,y);
            y=merge(tr[y].ch[0],tr[y].ch[1]);
            rt=merge(merge(x,y),z);
        }
        else if(opt==3) {
            split(rt,k-1,x,y);
            las=tr[x].size+1;
            ans^=las;
            rt=merge(x,y);
        }
        else if(opt==4) {
            las=val_by_rank(rt,k);
            ans^=las;
        }
        else if(opt==5) {
            split(rt,k-1,x,y);
            las=val_by_rank(x,tr[x].size);
            ans^=las;
            rt=merge(x,y);
        }
        else  {
            split(rt,k,x,y);
            las=val_by_rank(y,1);
            ans^=las;
            rt=merge(x,y);
        }
    }
    printf("%d\n",ans); 
    return 0;
}