记录

#include<cstdio>
#include<cstdlib>
#define N 100005
using namespace std;
struct pair
{
	int a,b;
};
int key[N],lson[N],rson[N],w[N],app[N];
int siz[N],rt,cnt,n,o,x,lst,t;
void pushup(int u) {siz[u]=siz[lson[u]]+siz[rson[u]]+app[u];}
int add(int k) {key[++cnt]=k;w[cnt]=rand();app[cnt]++;siz[cnt]=1;return cnt;}
int read()
{
	int ret=0;
	char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') 
	{
		ret=(ret<<3)+(ret<<1)+ch-'0';
		ch=getchar();
	}
	return ret;
}
int get(int v)
{
	if(!t) {return 0;}
	if(key[t]==v) {return siz[lson[t]]+1;}
	if(key[t]>v) {t=lson[t];return get(v);}
	//printf("%d %d %d\n",key[t],app[t],rson[t]);
	int ret=app[t]+siz[lson[t]];
	t=rson[t];
	//printf("%d %d %d\n",siz[lson[t]],get(v),app[t]);
	return get(v)+ret;
}
void split(int &l,int &r,int u,int k)//分裂 
{
	if(!u) {l=r=0;return;}
	if(k<=siz[lson[u]])//向左子树递归
	{	
		r=u;
		split(l,lson[u],lson[u],k);//引用指lsonu在下一层会被默认为r并赋值 
	}	
	else	
	{
		l=u;
		split(rson[u],r,rson[u],k-siz[lson[u]]-app[u]);//向右子树递归 
	}
	pushup(u);
}
int merge(int u,int v)//维护堆性质 （保持原BST性质不变->u,v相对位置不变) 
{
	if(!u || !v) return u+v;
	if(w[u]>=w[v]) 
	{
		lson[v]=merge(u,lson[v]);
		pushup(v);
		return v;
	} 
	else
	{
		rson[u]=merge(rson[u],v);
		pushup(u);
		return u;
	}
}
void insert(int k)//维护BST性质 (保持key升序) 
{
	if(!rt) 
	{
		rt=add(k);
		return;
	}
	t=rt;
	//printf("%d\n",t);
	int l,r,rr,s=get(k);
	//printf("%d %d\n",t,get(k));
	split(l,r,rt,s);split(l,rr,l,s-1);
	if(key[t]==k)
	{
		app[t]++;pushup(rr);
		rt=merge(merge(l,rr),r);
	} 
	else rt=merge(merge(merge(l,rr),add(k)),r);
}
int fore(int u,int x)
{
	if(!u) return -100000000;
	if(x<=key[u]) return fore(lson[u],x);
	int ret=fore(rson[u],x);
	if(ret<key[u]) return key[u];	
	return ret;
}	
int nex(int u,int x)
{
	if(!u) return 100000000;
	if(x>=key[u]) return nex(rson[u],x);
	int ret=nex(lson[u],x);
	if(ret>key[u]) return key[u];
	return ret;
}
void era(int k)
{
	t=rt;
	int pp=get(k),p1,p2,p3;
	split(p1,p2,rt,pp-1);split(p2,p3,p2,app[t]);
	if(app[t]>1) 
	{
		app[t]--;pushup(p2);
		rt=merge(p1,merge(p2,p3));
	}
	else rt=merge(p1,p3);
}
int kth(int u,int k)
{
	if(siz[lson[u]]+1<=k && siz[lson[u]]+app[u]>=k) return key[u];
	if(siz[lson[u]]>=k) return kth(lson[u],k);
	return kth(rson[u],k-siz[lson[u]]-app[u]);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		o=read();x=read();
		if(o==1) insert(x);
		if(o==2) era(x);
		if(o==3) 
		{
			t=rt;int ans=get(x);
			if(app[t]) printf("%d\n",ans);
			else printf("%d\n",ans+1);
		}
		if(o==4) printf("%d\n",kth(rt,x));
		if(o==5) printf("%d\n",fore(rt,x));
		if(o==6) printf("%d\n",nex(rt,x));
	}
	return 0;
}