求调Treap 60pts

#include<bits/stdc++.h>
using namespace std;
struct node{
	int lc,rc,key,pri,cnt,siz;
}t[100005];
int nodenum,root;
void pushup(int k){
	t[k].siz=t[t[k].lc].siz+t[t[k].rc].siz+t[k].cnt;
}
void lturn(int &k){
	int x=t[k].rc;
	t[k].rc=t[x].lc;
	t[x].lc=k;
	t[x].siz=t[k].siz;
	pushup(k);
	k=x;
}
void rturn(int &k){
	int x=t[k].lc;
	t[k].lc=t[x].rc;
	t[x].rc=k;
	t[x].siz=t[k].siz;
	pushup(k);
	k=x;
}
void insert(int &k,int key){
	if(!k){
		k=++nodenum;
		t[k].cnt=t[k].siz=1;
		t[k].key=key;
		t[k].pri=rand();
		t[k].lc=t[k].rc=0;
		return;
	}
	t[k].siz++;
	if(t[k].key==key)t[k].cnt++;
	else if(key<t[k].key){
		insert(t[k].lc,key);
		if(t[k].pri>t[t[k].lc].pri)rturn(k);
	}
	else{
		insert(t[k].rc,key);
		if(t[k].pri>t[t[k].rc].pri)lturn(k);
	}
}
int getpre(int key){
	int res=-1e9,now=root;
	while(now){
		if(t[now].key<=key)res=t[now].key,now=t[now].rc;
		else now=t[now].lc;
	}
	return res;
}
int getnxt(int key){
	int res=1e9,now=root;
	while(now){
		if(t[now].key>key)res=t[now].key,now=t[now].lc;
		else now=t[now].rc;
	}
	return res;
}
int queryrank(int &key){
	int x=root,res=0;
	while(x){
		if(key==t[x].key)return res+t[t[x].lc].siz+1;
		if(key<t[x].key)x=t[x].lc;
		else res+=t[t[x].lc].siz+t[x].cnt,x=t[x].rc;
	}
	return res;
}
int querykth(int k){
	int x=root;
	while(x){
		if(t[t[x].lc].siz<k&&t[t[x].lc].siz+t[x].cnt>=k)return t[x].key;
		if(t[t[x].lc].siz>=k)x=t[x].lc;
		else k-=t[t[x].lc].siz+t[x].cnt,x=t[x].rc;
	}
	return 0;
}
void del(int &k,int key){
	if(t[k].key==key){
		if(t[k].cnt>1)t[k].cnt--,t[k].siz--;
		else if(!t[k].lc||!t[k].rc)k=t[k].lc+t[k].rc;
		else if(t[t[k].lc].pri<t[t[k].rc].pri){
			rturn(k);
			del(k,key);
		}
		else{
			lturn(k);
			del(k,key);
		}
		return;
	}
	t[k].siz--;
	if(key<t[k].key)del(t[k].lc,key);
	else del(t[k].rc,key);
}
int main(){
	int n;
	scanf("%d",&n);
	int x,op;
	while(n--){
		scanf("%d%d",&op,&x);
		if(op==1){
			insert(root,x);
		}
		else if(op==2){
			del(root,x);
		}
		else if(op==3){
			printf("%d\n",queryrank(x));
		}
		else if(op==4){
			printf("%d\n",querykth(x));
		}
		else if(op==5){
			printf("%d\n",getpre(x));
		}
		else if(op==6){
			printf("%d\n",getnxt(x));
		}
	}
	return 0;
}