平衡树Treap求助 44tps

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>

#define ls(p) tr[p].pl
#define rs(p) tr[p].pr
#define val(p) tr[p].val
#define rnd(p) tr[p].rnd
#define size(p) tr[p].size
#define push_up(p) size(p)=size(ls(p))+size(rs(p))+1
#define N 2000010
#define ll long long
#define INF 0x3f3f3f3f

ll n,m,op,x,last,root,cnt,ans;
struct Treap{
	ll pl,pr;
	ll val,rnd;
	ll size;
};
Treap tr[N];

ll read();
void newnode(ll val);
void split(ll rt,ll k,ll &x,ll &y);
void merge(ll &rt,ll x,ll y); 
void insert(ll rt,ll k);
void del(ll rt,ll k);
ll Ntr(ll rt,ll k);
ll Rtn(ll rt,ll k);
ll qq(ll rt,ll k);
ll hq(ll rt,ll k);

int main(){
	n=read(),m=read();
	srand(time(0));
	root=1;
	newnode(INF);
	rnd(root)=-INF;	
	for(int i=1;i<=n;i++){
		ll val=read();
		insert(root,val);
	}
	for(int i=1;i<=m;i++){
		op=read(),x=read();
		if(op==1)insert(root,x^last);
		if(op==2)del(root,x^last);
		if(op==3){
			last=Ntr(root,x^last);
			ans^=last;
		}
		if(op==4){
			last=Rtn(root,x^last);
			ans^=last;
		}
		if(op==5){
			last=qq(root,x^last);
			ans^=last;
		}
		if(op==6){
			last=hq(root,x^last);
			ans^=last;
		}
	}
	std::cout<<ans<<"\n";
	return 0;
}
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void newnode(ll val){
	cnt++;
	size(cnt)=1;
	val(cnt)=val;
	rnd(cnt)=rand();
}
void split(ll rt,ll k,ll &x,ll &y){
	if(rt==0){
		x=0;
		y=0;
		return ;	
	}	
	if(val(rt)<=k){
		x=rt;
		split(rs(rt),k,rs(x),y);
	}
	else{
		y=rt;
		split(ls(rt),k,x,ls(y)); 
	}
	push_up(rt);
}
void merge(ll &rt,ll x,ll y){
	if(!x||!y){
		rt=x+y;
		return ;	
	}	
	if(rnd(x)<=rnd(y)){
		rt=x;
		merge(rs(rt),rs(x),y);
	}
	else{
		rt=y;
		merge(ls(y),x,ls(y));	
	}
	push_up(rt);
} 
void insert(ll rt,ll k){
	ll px=0,py=0;
	newnode(k); 
	split(rt,k-1,px,py);
	merge(px,px,cnt);
	merge(rt,px,py);
}
void del(ll rt,ll k){
	ll px=0,py=0,pz=0;
	split(rt,k,px,py);
	split(px,k-1,px,pz);
	merge(pz,ls(pz),rs(pz));
	merge(px,px,pz);
	merge(rt,px,py);
}
ll Ntr(ll rt,ll k){
	ll px=0,py=0,jg=0;
	split(rt,k,px,py);
	jg=size(px)+1;
	merge(rt,px,py);
	return jg;
}
ll Rtn(ll rt,ll k){
	if(size(ls(rt))+1==k)return val(rt);
	if(size(ls(rt))>=k)return Ntr(ls(rt),k);
	else return Ntr(rs(rt),k-size(ls(rt))-1);
}
ll qq(ll rt,ll k){
	ll px=0,py=0,jg=0;
	split(rt,k-1,px,py);
	jg=Rtn(px,size(px));
	merge(rt,px,py);
	return jg;
	
}
ll hq(ll rt,ll k)
{
	ll px=0,py=0,jg=0;
	split(rt,k,px,py);
	jg=Rtn(py,1);
	merge(rt,px,py);
	return jg;
}