求调treap树QWQ

#include<bits/stdc++.h>
using namespace std;
int cnt=0;
struct node{
	int ls,rs,size,val,lev;
}tree[414514];
int Precursor(int u,int x){
	if(u==0) return 0;    
	if(tree[u].val>=x) return Precursor(tree[u].ls,x);   //前驱必定在左子树上 
	int n=Precursor(tree[u].rs,x);  
	if(n==0) return tree[u].val;   //x是右子树上最小的数(前驱为当前节点) 
	return n; 
}
int Successor(int u,int x){
	if(u==0) return 0;    
	if(tree[u].val<=x) return Successor(tree[u].rs,x);   //后继必定在右子树上 
	int n=Successor(tree[u].ls,x);  
	if(n==0) return tree[u].val;   //x是左子树上最大的数(后继为当前节点) 
	return n; 
}
int Rank(int u,int x){
	if(u==0) return 0;
	if(x>tree[u].val) return tree[tree[u].ls].size+1+Rank(tree[u].rs,x);
	return Rank(tree[u].ls,x);
}
int kth(int u,int k){
	if(k==tree[tree[u].ls].size+1) return tree[u].val;   //当前节点在 以这个节点为根节点的树 上排名为k
	if(k>tree[tree[u].ls].size+1) return kth(tree[u].rs,k-tree[tree[u].ls].size-1); //当前节点在 右子树 上 
	if(k<=tree[tree[u].ls].size) return kth(tree[u].ls,k); //当前节点在 左子树 上 
}
void rotate(int &o,bool d){
	int k;       //暂存旋转的节点序号
	if(d==1){
		k=tree[o].rs;
		tree[o].rs=tree[k].ls;
		tree[k].ls=o;
	}else{
		k=tree[o].ls;
		tree[o].ls=tree[k].rs;
		tree[k].rs=o;
	}
	tree[k].size=tree[o].size;
	tree[o].size=tree[tree[o].ls].size+tree[tree[o].rs].size;  //旋转之后节点的size值会有变化，所以要更新
	o=k;
	return;
}
void made(int x){
	cnt++;
	tree[cnt].ls=tree[cnt].rs=0;
	tree[cnt].val=x;
	tree[cnt].size=1;
	tree[cnt].lev=rand(); //优先级随机赋值 
	return;
}
void join(int x,int &u){
	if(u==0){
		made(x);
		u=cnt;
		return;
	}
	tree[u].size++;
	if(x>=tree[u].val) join(x,tree[u].rs);
	else join(x,tree[u].ls);
	if(tree[u].ls !=0 && tree[u].lev<tree[tree[u].ls].lev) rotate(u,1); //左旋 
	if(tree[u].rs !=0 && tree[u].lev<tree[tree[u].rs].lev) rotate(u,0); //右旋 
	tree[u].size=tree[tree[u].ls].size+tree[tree[u].rs].size; //添加之后节点的size值会有变化，所以要更新 
	return;
}
void del(int x,int &u){
	tree[u].size--;
	if(tree[u].val==x){
		if(tree[u].ls==0&&tree[u].rs==0) u=0;//可以试试size==0 
		else if(tree[u].ls==0||tree[u].rs==0) u=tree[u].ls+tree[u].rs;//u的左(右)节点代替u
		else if(tree[tree[u].ls].lev>tree[tree[u].rs].lev){
			rotate(u,0);
			del(x,tree[u].rs);
		}else{
			rotate(u,1);
			del(x,tree[u].ls);
		}
		return;
	}
	if(tree[u].val>=x) del(x,tree[u].ls);
	else del(x,tree[u].rs);
	tree[u].size=tree[tree[u].ls].size+tree[tree[u].rs].size; //日常更新 
	return;
}
int main(){
	srand(time(NULL));
	int n;
	cin>>n;
	int root=0;
	while(n--){
		int cz,x;
		cin>>cz>>x;
		if(cz==1) join(x,root);
		if(cz==2) del(x,root);
		if(cz==3) cout<<Rank(root,x)+1<<endl;
		if(cz==4) cout<<kth(root,x)<<endl;
		if(cz==5) cout<<Precursor(root,x)<<endl;
		if(cz==6) cout<<Successor(root,x)<<endl;
	}
	return 0;
}