不开O2 MLE*10+WA*2 提交记录
开O2 TLE*10+WA*2 提交记录
CP Editor前四个测试点测试均为AC

#include<bits/stdc++.h>
using namespace std;
struct BST{
	int l,r,val,rnd,w,size;
}bst[1000005];
int n,tot,root;
void update(int x) {
	bst[x].size=bst[bst[x].r].size+bst[bst[x].l].size+bst[x].w;
	return;
}
void change_anc(int k,int anc,bool b){
	if(b) bst[anc].r=k;
	else bst[anc].l=k;
}
int newpoint(int val){
	bst[++tot].val=val;
	bst[tot].rnd=rand();
	bst[tot].w++;
	bst[tot].size++;
	return tot;
}
void build(){
	bst[0].size=0;
	root=newpoint(-1000000000);
	bst[root].r=newpoint(100000000);
	update(root);
}
int zig(int p,int anc,bool b){
	int q=bst[p].l;
	bst[p].l=bst[q].r;
	bst[q].r=p;
	change_anc(q,anc,b);
	
	update(p);
	update(q);
	return q;
}
int zag(int p,int anc,bool b){
	int q=bst[p].r;
	bst[p].r=bst[q].l;
	bst[q].l=p;
	change_anc(q,anc,b);
	
	update(p);
	update(q);
	return q;
}
void insert(int k,int p,int anc,bool b){
	// cout<<k<<" ";
	if(!k){
		k=newpoint(p);
		change_anc(k,anc,b);
		return;
	}
	else if(bst[k].val==p) bst[k].w++;
	else if(bst[k].val<p){
		insert(bst[k].r,p,k,1);
		if(bst[k].rnd>bst[bst[k].r].rnd) zag(k,anc,b);
	}
	else{
		insert(bst[k].l,p,k,0);
		if(bst[k].rnd>bst[bst[k].l].rnd) zig(k,anc,b);
	}
	update(k);
}
void del(int k,int val,int anc,bool b){
	if(!k) return ;
	else if(val==bst[k].val){
		if(bst[k].w>1) {
			bst[k].w--;
			return;
		}
		else{
			if(bst[k].l==0||bst[k].r==0) change_anc(bst[k].l+bst[k].r,anc,b);
			else{
				if(bst[bst[k].l].rnd<bst[bst[k].r].rnd){
					k=zig(k,anc,b);
					del(bst[k].r,val,k,1);
				}
				else{
					k=zag(k,anc,b);
					del(bst[k].l,val,k,0);
				}
			}
		}
	}
	else if(bst[k].val<val) del(bst[k].r,val,k,1);
	else del(bst[k].l,val,k,0);
	update(k);
	return;
}
int get_rank(int k,int val){
	// cout<<k;
	if(!k) return 0;
	else if(val==bst[k].val) return bst[bst[k].l].size;
	else if(val<bst[k].val) return get_rank(bst[k].l,val);
	else return get_rank(bst[k].r,val)+bst[bst[k].l].size+bst[k].w;
}
int get_val(int k,int rk){
	// cout<<k;
	if(!k) return 100000000;
	else if(rk<=bst[bst[k].l].size) return get_val(bst[k].l,rk);
	else if(rk<=bst[bst[k].l].size+bst[k].w) return bst[k].val;
	else return get_val(bst[k].r,rk-bst[bst[k].l].size-bst[k].w);
}
int get_pre(int val){
	int k=root;
	int ans=-100000000;
	while(k){
		if(val>bst[k].val){
			ans=bst[k].val;
			k=bst[k].r;
		}
		else k=bst[k].l;
	}
	return ans;
}
int get_next(int val){
	int k=root;
	int ans=100000000;
	while(k){
		if(val<bst[k].val){
			ans=bst[k].val;
			k=bst[k].l;
		}
		else k=bst[k].r;
	}
	return ans;
}
int main(){
	build();
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int q,x;
		scanf("%d%d",&q,&x);
		if(q==1) insert(root,x,root,0);
		else if(q==2) del(root,x,root,0);
		else if(q==3) printf("%d\n",get_rank(root,x));
		else if(q==4) printf("%d\n",get_val(root,x+1));
		else if(q==5) printf("%d\n",get_pre(x));
		else if(q==6) printf("%d\n",get_next(x));
	}
	return 0;
}