fhq非旋Treap T了第一个点，求助

根据目前的测试结果，第一个点先有大约5e5个insert操作，然后是5e5个delete操作，最后一个是4操作

前面insert运行速度还可以，但后面Delete明显很慢，本机大概20s+出答案，答案是正确的

提交记录与代码

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define ll long long
int n,m;
ll lst,ans;
class Treap{
    public:
    int root,tot;
    class node{
        public:
        int l,r,size;
        ll v;
    }a[1100010];
    Treap(){
        root=tot=0;
    }void up(int x){
        if(x!=0)a[x].size=a[a[x].l].size+a[a[x].r].size+1;
    }int newnode(ll val){
        a[++tot].v=val;
        a[tot].size=1;
        return tot;
    }void split(int p,ll val,int &x,int &y){
        if(p==0)x=y=0;
        else if(a[p].v<=val)x=p,split(a[p].r,val,a[p].r,y);
        else y=p,split(a[p].l,val,x,a[p].l);
        up(p);
        return;
    }int merge(int x,int y){
        if(!x||!y)return x+y;
        int rd=std::rand()%(a[x].size+a[y].size);
        int l=a[y].l,r=a[x].r;
        if(rd<a[x].size){
            a[x].r=y;
            a[y].l=merge(r,l);
            up(y),up(x);
            return x;
        }else {
            a[y].l=x;
            a[x].r=merge(r,l);
            up(x),up(y);
            return y;
        }
    }void insert(ll val){
        int x,y;
        split(root,val,x,y);
        root=merge(merge(x,newnode(val)),y);
        return;
    }void Delete(ll val){
        int x,y,z;
        split(root,val,x,z);
        split(x,val-1,x,y);
        y=merge(a[y].l,a[y].r);
        root=merge(merge(x,y),z);
        return;
    }int rank(ll val){
        int x,y,rk;
        split(root,val-1,x,y);
        rk=a[x].size;
        root=merge(x,y);
        return rk;
    }int rerank(int x,int rk){
        while(x){
            if(a[a[x].l].size>rk)x=a[x].l;
            else if(a[a[x].l].size==rk)break;
            else rk-=a[a[x].l].size+1,x=a[x].r;
        }return x;
    }int fpre(ll val){
        int x,y,an;
        split(root,val-1,x,y);
        an=rerank(x,a[x].size-1);
        root=merge(x,y);
        return an;
    }int fnxt(ll val){
        int x,y,an;
        split(root,val,x,y);
        an=rerank(y,0);
        root=merge(x,y);
        return an;
    }
}bt;
int main(){
    std::srand(time(NULL));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        ll val;
        scanf("%lld",&val);
        bt.insert(val);
    }
    for(int i=1;i<=m;i++){
        ll opt,x;
        scanf("%lld%lld",&opt,&x);
        x^=lst;
        if(opt==1)bt.insert(x);
        if(opt==2)bt.Delete(x);
        if(opt==3)lst=bt.rank(x)+1;
        if(opt==4)lst=bt.a[bt.rerank(bt.root,x-1)].v;
        if(opt==5)lst=bt.a[bt.fpre(x)].v;
        if(opt==6)lst=bt.a[bt.fnxt(x)].v;
        if(opt>=3)ans^=lst;
    }printf("%lld",ans);
    return 0;
}