FHQ treap TLE 求调

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n,root,tot;
int siz[maxn+5],val[maxn+5],key[maxn+5],lc[maxn+5],rc[maxn+5];
int newnode(int v){
	val[++tot]=v,key[tot]=rand(),siz[tot]=1;
	return tot;
}
void update(int x){
	siz[x]=siz[lc[x]]+siz[rc[x]]+1;
}
void split(int x,int k,int &a,int &b){
	if(x==0){
		a=b=0;
		return;
	}
	if(val[x]<=k){
		a=x;
		split(rc[a],k,rc[a],b);
		update(a);
	}
	else{
		b=x;
		split(lc[b],k,a,lc[b]);
		update(b);
	}
}
int merge(int a,int b){
	if(a==0||b==0){
		return a+b;
	}
	if(key[a]<key[b]){
		rc[a]=merge(rc[a],b);
		update(a);
		return a;
	}
	else{
		lc[b]=merge(a,lc[b]);
		update(b);
		return b;
	}
}
void insert(int x){
	int a,b;
	split(root,x,a,b);
	root=merge(merge(a,newnode(x)),b);
}
void del(int x){
	int a,b,c;
	split(root,x,a,c);
	split(a,x-1,a,b);
	b=merge(lc[b],rc[b]);
	root=merge(merge(a,b),c);
}
int getrank(int x){
	int a,b,ans;
	split(root,x-1,a,b);
	ans=siz[a]+1;
	root=merge(a,b);
	return ans;
}
int getvalue(int x,int k){
	if(siz[lc[x]]+1==k){
		return val[x];
	}
	else if(siz[lc[x]]>k){
		return getvalue(lc[x],k);
	}
	else{
		return getvalue(rc[x],k-siz[lc[x]]-1);
	}
}
int getpre(int x){
	int a,b,p,ans;
	split(root,x-1,a,b);
	p=a;
	while(rc[p]!=0){
		p=rc[p];
	}
	ans=val[p];
	root=merge(a,b);
	return ans;
}
int getnext(int x){
	int a,b,p,ans;
	split(root,x,a,b);
	p=b;
	while(lc[p]!=0){
		p=lc[p];
	}
	ans=val[p];
	root=merge(a,b);
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int op,x;
		scanf("%d %d",&op,&x);
		switch(op){
			case 1:
				insert(x);
				break;
			case 2:
				del(x);
				break;
			case 3:
				printf("%d\n",getrank(x));
				break;
			case 4:
				printf("%d\n",getvalue(root,x));
				break;
			case 5:
				printf("%d\n",getpre(x));
				break;
			case 6:
				printf("%d\n",getnext(x));
				break;
		}
	}
	return 0;
}