60WA

马蜂略毒瘤/jk

#include<cstdio>
#include<iostream>
using namespace std;
int n,root,tot;
struct str
{
	int son[2],cnt,f,value,size;
}t[114514<<1];
void rotate(int x)
{
	int fa=t[x].f,gfa=t[fa].f;
	int k=(t[fa].son[1]==x)?1:0;
	t[gfa].son[t[gfa].son[1]==fa?1:0]=x;
	t[x].f=gfa;
	t[fa].son[k]=t[x].son[k^1];
	t[t[x].son[k^1]].f=fa;
	t[x].son[k^1]=fa;
	t[fa].f=x;
	t[x].size=t[t[x].son[1]].size+t[t[x].son[0]].size+t[x].cnt;
	t[fa].size=t[t[fa].son[1]].size+t[t[fa].son[0]].size+t[fa].cnt;
}
void splay(int x,int r)
{
	while(t[x].f!=r)
	{
		int fa=t[x].f,gfa=t[fa].f;
		if(gfa!=r) (t[gfa].son[0]==fa)^(t[fa].son[0]==x)?rotate(x):rotate(fa);
		rotate(x);
	}
	if(r==0) root=x;
}
void find(int x) 
{
	if(!root) return;
	int k=root;
	while(t[k].son[x>t[k].value?1:0]&&x!=t[k].value)
	k=t[k].son[x>t[k].value?1:0];
	splay(k,0);
}
void insert(int x)
{
	int k=root,fa=0;
	while(k&&t[k].value!=x)
	{
		fa=k;
		k=t[k].son[x>t[k].value?1:0];
	}
	if(k) t[k].cnt++;
	else
	{
		++tot;
		if(fa) t[fa].son[x>t[fa].value?1:0]=tot;
		t[tot].son[0]=t[tot].son[1]=0;
		t[tot].f=fa;
		t[tot].value=x;
		t[tot].cnt=1;
		t[tot].size=1;
	}
	splay(tot,0);
}
int next(int x,int s)
{
	find(x);
	int k=root;
	if(t[k].value>x&&s) return k;
	if(t[k].value<x&&!s) return k;
	k=t[k].son[s];
	while(t[k].son[s^1]) k=t[k].son[s^1];
	return k;
}
void del(int x)
{
	int la=next(x,0),ne=next(x,1);
	splay(la,0),splay(ne,la);
	int k=t[ne].son[0];
	if(t[k].cnt>1)
	{
		t[k].cnt--;
		splay(k,0);
	}
	else t[ne].son[0]=0;
}
int query(int x)
{
	int k=root;
	if(t[k].size<x) return 0;
	while(1)
	{
		int lson=t[k].son[0],rson=t[k].son[1],sum=t[lson].size+t[k].cnt;
		if(x>sum)
		{
			x-=sum;
			k=rson;
		}
		else
		{
			if(t[lson].size>=x) k=lson;
			else return t[k].value;
		}
	}
}
int main()
{
	scanf("%d",&n);
	insert(0x7fffffff);
	insert(-0x7fffffff);
	while(n--)
	{
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1) insert(x);
		if(opt==2) del(x);
		if(opt==3)
		{
			find(x);
			printf("%d\n",t[t[root].son[0]].size);
		}
		if(opt==4) printf("%d\n",query(x+1));
		if(opt==5) printf("%d\n",t[next(x,0)].value);
		if(opt==6) printf("%d\n",t[next(x,1)].value);
	}
	return 0;
}