treap树求调 7分

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5;
const int INF = 0x3f3f3f3f;
#define int long long 
struct node{
	int l,r;
	int val,pri;
	int cnt,size;
}tree[maxn];
int n,tot,root;
int NEW(int val){
	tree[++tot].val=val;
	tree[tot].pri=rand();
	tree[tot].cnt=tree[tot].size=1;
	tree[tot].l=tree[tot].r=0;
	return tot;
}

void update(int p){
	tree[p].size=tree[tree[p].l].size+tree[tree[p].r].size+tree[p].cnt;
}

void build(){
	NEW(-INF); NEW(INF);
	root=1,tree[1].r=2;
	update(root);
}

void zig(int &p){
	int q=tree[p].l;
	tree[p].l=tree[q].r;
	tree[q].r=p;
	p=q;
	update(tree[p].r);
	update(p);
}

void zag(int &p){
	int q=tree[p].r;
	tree[p].r=tree[q].l;
	tree[q].l=p;
	p=q;
	update(tree[p].l);
	update(p);
}

void inst(int &p,int val){
	if(!p){
		p=NEW(val);
		return;
	}
	if(val==tree[p].val){
		tree[p].cnt++,update(p);
		return;
	}
	if(val<tree[p].val){
		inst(tree[p].l,val);
		if(tree[p].pri<tree[tree[p].l].pri) zig(p);		
	}
	else{
		inst(tree[p].r,val);
		if(tree[p].pri<tree[tree[p].r].pri) zag(p);
	}
	update(p);
}

void del(int &p,int val){
	if(!p) return;
	if(val==tree[p].val){
		if(tree[p].cnt>1){
			tree[p].cnt--; update(p);
			return;
		}
		if(tree[p].l || tree[p].r){
			if(!tree[p].r || tree[tree[p].l].pri>tree[tree[p].r].pri){
				zig(p);
				del(tree[p].r,val);
			}
			else{
				zag(p);
				del(tree[p].r,val);
			}
			update(p);
		}
	}
	else{
		p=0;
		return ;
	}
	if(val<tree[p].val){
		del(tree[p].l,val);
	}
	else{
		del(tree[p].r,val);
	}
	update(p);
}

int findrank(int p,int val){
	if(!p) return 0;
	if(val==tree[p].val) return tree[tree[p].l].size+1;
	if(val<tree[p].val) return findrank(tree[p].l,val);
	return findrank(tree[p].r,val-tree[tree[p].l].size-tree[p].cnt);
}

int findval(int p,int rank){
	if(!p) return INF;
	if(tree[tree[p].l].size>=rank) return findval(tree[p].l,rank);
	if(tree[tree[p].l].size+tree[p].cnt>=rank) return tree[p].val;
	return findval(tree[p].r,rank-tree[tree[p].l].size-tree[p].cnt);
}

int findmin(int val){
	int ans=1;
	int p=root;
	while(p){
		if(val==tree[p].val){
			if(tree[p].l>0){
				p=tree[p].l;
				while(tree[p].r>0) p=tree[p].r;
				ans=p;
			}
			break;
		}
		if(tree[p].val<val&&tree[p].val>tree[ans].val) ans=p;
		p=val<tree[p].val?tree[p].l:tree[p].r;
	}
	return tree[ans].val;
}

int findmax(int val){
	int ans=2;
	int p=root;
	while(p){
		if(val==tree[p].val){
			if(tree[p].r>0){
				p=tree[p].r;
				while(tree[p].l>0) p=tree[p].l;
				ans=p;
			}
			break;
		}
		if(tree[p].val<val&&tree[p].val>tree[ans].val) ans=p;
		p=val<tree[p].val?tree[p].l:tree[p].r;
	}
	return tree[ans].val;
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	build();
	for(int i=1;i<=n;i++){
		int op,x;
		cin>>op>>x;
		switch(op){
			case 1:inst(root,x); break;
			case 2:del(root,x); break;
			case 3:printf("%lld\n",findrank(root,x)); break;
			case 4:printf("%lld\n",findval(root,x)); break;
			case 5:printf("%lld\n",findmin(x)); break;
			case 6:printf("%lld\n",findmax(x)); break;
		}
	}
	return 0;
}