Treap 求调

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7f7f7f7f
#define map unorded_map
#define re register
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define Mod 998244353
#define F1(i,a,b,k) for(re int i=a;i<=b;i+=k)
#define F2(i,a,b,k) for(re int i=a;i>=b;i-=k)
namespace Fast_Io{
	template<typename T> inline void read(T &t){
	    t=0;
	    char c=getchar();
	    int f=1;
	    while(!isdigit(c)){
	        if(c=='-') f=-f;
	        c=getchar();
	    }
	    while(isdigit(c)){
	        t=(t<<3)+(t<<1)+(c^'0');
	        c=getchar();
	    }
	    t*=f;
	}
	template<typename T,typename ... Args> inline void read(T &t,Args&... args){
	    read(t);
	    read(args...);
	}
	template<typename T> inline void print(T x,char c='\0'){
	    if(x<0){
	        x=-x;
	        putchar('-');
	    }
	    if(x>9){
	        print(x/10);
	    }
		putchar(x%10+'0');
		if(c!='\0'){
			putchar(c);
		}
	}
	template<typename T> inline T abs(T x){return x<0?-x:x;}
	inline int lowbit(int x){return x&(-x);}
}
using namespace Fast_Io;
const int N = 600005;
struct Treap{
	// val -> BST key -> heap
	int lc,rc,sz,key,val,cnt;
}tr[N];
int tot,m,abc,root=0,op;
inline void pushup(int p){
	tr[p].sz=tr[tr[p].lc].sz+tr[tr[p].rc].sz+tr[p].cnt;
}
inline void RRotate(int &f){
	int t=tr[f].lc;
	tr[f].lc=tr[t].rc;
	tr[t].rc=f;
	tr[t].sz=tr[f].sz;
	pushup(f);
	f=t;
}
inline void LRotate(int &f){
	int t=tr[f].rc;
	tr[f].rc=tr[t].lc;
	tr[t].lc=f;
	tr[t].sz=tr[f].sz;
	pushup(f);
	f=t;
}
inline int New(int d){
	tr[++tot].val=d;
	tr[tot].key=rand();
	tr[tot].sz=1;
	tr[tot].cnt=1;
	tr[tot].lc=0;
	tr[tot].rc=0;
	return tot;
}
inline void ins(int &c,int x){
	if(c==0){
		c=New(x);
		return ;
	}
	if(x==tr[c].val){
		tr[c].cnt++;
	}else if(x>tr[c].val){
		ins(tr[c].rc,x);
	}else{
		ins(tr[c].lc,x);
	}
	if(tr[c].lc!=0 && tr[c].key>tr[tr[c].lc].key) RRotate(c);
	if(tr[c].rc!=0 && tr[c].key>tr[tr[c].rc].key) LRotate(c);
	pushup(c);
}
inline void erase(int &c,int x){
	if(c==0) return ;
	if(x==tr[c].val){
		if(tr[c].cnt>=2){tr[c].cnt--;pushup(c);return ;}
		if(tr[c].lc!=0 || tr[c].rc!=0){
			if(tr[c].rc==0 || tr[tr[c].rc].key>tr[tr[c].lc].key){
				RRotate(c);
				erase(tr[c].rc,x);
			}else{
				LRotate(c);
				erase(tr[c].lc,x);
			}
			pushup(c);
		}else{
			c=0;
			return ;
		}
	}
	if(x<tr[c].key) erase(tr[c].lc,x);
	else erase(tr[c].rc,x);
	pushup(c);
}
int Rank(int c,int x){
	if(c==0) return 1;
	if(x==tr[c].val) return tr[tr[c].lc].sz+1;
	else if(x<tr[c].val) return Rank(tr[c].lc,x);
	else{
		int tmp=Rank(tr[c].rc,x);
		return tr[tr[c].lc].sz+tr[c].cnt+tmp;
	}
}
int kth(int c,int x){
	if(x<=tr[tr[c].lc].sz) return kth(tr[c].lc,x);
	else if(x<=tr[tr[c].lc].sz+tr[c].cnt) return tr[c].val;
	else return kth(tr[c].rc,x-tr[tr[c].lc].sz-tr[c].cnt);
}
inline int Front(int c,int x){
	int ans=0;
	while(c){
		if(tr[c].val<x){
			ans=tr[c].val;
			c=tr[c].rc;
		}else{
			c=tr[c].lc;
		}
	}
	return ans;
}
inline int Back(int c,int x){
	int ans=0;
	while(c){
		if(tr[c].val>x){
			ans=tr[c].val;
			c=tr[c].lc;
		}else{
			c=tr[c].rc;
		}
	}
	return ans;
}
int main(){
	srand(time(0));
	read(m);
	while(m--){	
		read(op,abc);
		if(op==1){
			ins(root,abc);
		}else if(op==2){
			erase(root,abc);
		}else if(op==3){
			int Ans=Rank(root,abc);
			cout<<Ans<<endl;
		}else if(op==4){	
			int Ans=kth(root,abc);
			cout<<Ans<<endl;
		}else if(op==5){
			int Ans=Front(root,abc);
			cout<<Ans<<endl;
		}else{
			int Ans=Back(root,abc);
			cout<<Ans<<endl;
		}
	}
	return 0;
}