记录编号	295944	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.521 s
提交时间	2016-08-14 18:55:32	内存使用	1.83 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
struct Node{
	int f,c[2],size,cnt,x;
}t[100100];
int n,x,y,root,size;
void Up(int p)
{
	t[p].size=t[ t[p].c[0] ].size+t[ t[p].c[1] ].size+t[p].cnt;
}
void Rot(int p,bool b)
{
	int x=t[p].f;
	int y=t[p].c[b];
	int z=t[y].c[!b];
	t[x].c[t[x].c[0]!=p]=y;
	if(y)
	  t[y].f=x;
	t[y].c[!b]=p;
	if(p)
	  t[p].f=y;
	t[p].c[b]=z;
	if(z)
	  t[z].f=p;
	Up(p);
	Up(y);	
}
void Splay(int p)
{
	int x=t[p].f;
	int y=t[x].f;
	if(!x)return;
	if(!y)
	{
		Rot(x,t[x].c[0]!=p);
		return;
	}
	if( ( t[x].c[0]==p )^( t[y].c[0]==x ))
	{
		Rot(x,t[x].c[0]!=p);
		Rot(y,t[y].c[0]!=p);
		Splay(p);
	//	return;
	}
	else
	{
		Rot(y,t[y].c[0]!=x);
		Rot(x,t[x].c[0]!=p);
		Splay(p);
	//	return;
	}
}
void Insert(int p,int x,int f,bool b)
{
	if(p==0)
	{
		p=++size;
		t[f].c[b]=p;
		t[p].f=f;
		t[p].x=x;
		t[p].size=t[p].cnt=1;
		Splay(p);
		return;
	}
	t[p].size++;
	if(t[p].x==x)
	{
		t[p].cnt++;
		Splay(p);
		return;
	}
	Insert(t[p].c[ x>t[p].x ],x,p,x>t[p].x);
}
void del(int p,int x,int f,int b)
{
	if(t[p].x==x)
	{
		if(t[p].cnt>1)
		{
			t[p].size--;
			t[p].cnt--;
			return;
		}
		if(t[p].c[0]==0&&t[p].c[1]==0)
		{
			t[f].c[b]=0;
			return;
		}
		if(t[p].c[0]*t[p].c[1]==0)
		{
			t[f].c[b]=t[p].c[0]+t[p].c[1];
			if(t[p].c[0])
			  t[ t[p].c[0] ].f=f;
			else 
			  t[ t[p].c[1] ].f=f;
			return;
		}
		Rot(p,t[t[p].c[1]].size<t[t[p].c[0]].size);
		t[t[p].f].size--;
		del(p,x,t[p].f,t[t[p].f].c[0]!=p);
		return;
	}
	t[p].size--;
	del(t[p].c[x>t[p].x],x,p,x>t[p].x);
}
int rank(int p,int x)
{
	if(p==0)return 0;
	if(x<t[p].x)return rank(t[p].c[0],x);
	if(t[p].x==x)
	{
		int ans=t[t[p].c[0]].size+1;
		Splay(p);
		return ans;
	}
	return t[t[p].c[0]].size+t[p].cnt+rank(t[p].c[1],x);
}
int query(int p,int x)
{
	if(p==0)return 0;
	if(x<=t[t[p].c[0]].size)return query(t[p].c[0],x);
	if(x<=t[t[p].c[0]].size+t[p].cnt)
	{
		Splay(p);
		return t[p].x;
	}
	return query(t[p].c[1],x-t[ t[p].c[0] ].size-t[p].cnt);
}
int pre(int p,int x)
{
	if(p==0)return -1;
	if(t[p].x<x)
	{
		int y=pre(t[p].c[1],x);
		if(y==-1)
		{
			Splay(p);
			return t[p].x;
		}
		return y;
	}
	return pre(t[p].c[0],x);
}
int suc(int p,int x)
{
	if(p==0)return -1;
	if(t[p].x>x)
	{
		int y=suc(t[p].c[0],x);
		if(y==-1)
		{
			Splay(p);
			return t[p].x;
		}
		return y;
	}
	return suc(t[p].c[1],x);
}
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if(x==1)Insert(t[0].c[0],y,0,0);
		if(x==2)del(t[0].c[0],y,0,0);
		if(x==3)printf("%d\n",rank(t[0].c[0],y));
		if(x==4)printf("%d\n",query(t[0].c[0],y));
		if(x==5)printf("%d\n",pre(t[0].c[0],y));
		if(x==6)printf("%d\n",suc(t[0].c[0],y));
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}