记录编号	217151	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	nieyunhe	是否通过	通过
代码语言	C++	运行时间	0.216 s
提交时间	2016-01-02 15:14:03	内存使用	1.84 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
struct data{
	int ls,rs,sum,val;
}tr[N];
int tot=0,root=0;
inline void l_rotate(int &x)
{
	int y=tr[x].rs;
	tr[x].rs=tr[y].ls;
	tr[y].ls=x;
	tr[y].sum=tr[x].sum;
	tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum+1;
	x=y;
}
inline void r_rotate(int &x)
{
	int y=tr[x].ls;
	tr[x].ls=tr[y].rs;
	tr[y].rs=x;
	tr[y].sum=tr[x].sum;
	tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum+1;
	x=y;
}
inline void Maintain(int &x,bool flag)
{
	if(!flag)
	{
		if(tr[tr[tr[x].ls].ls].sum>tr[tr[x].rs].sum)
		r_rotate(x);
		else if(tr[tr[tr[x].ls].rs].sum>tr[tr[x].rs].sum)
		l_rotate(tr[x].ls),r_rotate(x);
		else return ;
	}
	else
	{
		if(tr[tr[tr[x].rs].rs].sum>tr[tr[x].ls].sum)
		l_rotate(x);
		else if(tr[tr[tr[x].rs].ls].sum>tr[tr[x].ls].sum)
		r_rotate(tr[x].rs),l_rotate(x);
		else return ;
	}
	Maintain(tr[x].ls,0);
	Maintain(tr[x].rs,1);
	Maintain(x,1);Maintain(x,0);
}
inline void insert(int &x,int d)//插入 
{
	if(!x)
	{
		x=++tot;
		tr[x].val=d;
		tr[x].ls=0,tr[x].rs=0;
		tr[x].sum=1;
		return;
	}
	tr[x].sum++;
	if(d<=tr[x].val)insert(tr[x].ls,d);
	else insert(tr[x].rs,d);
	Maintain(x,d>tr[x].val);
}
inline int del(int &x,int d)//删掉值为d的点，把他的接近点提到他的位置上 
{
	int ans;
	tr[x].sum--;
	if(d==tr[x].val||(d<tr[x].val&&!tr[x].ls)||(d>tr[x].val&&!tr[x].rs))
	{
		ans=tr[x].val;
		if(!tr[x].ls||!tr[x].rs)x=tr[x].ls+tr[x].rs;
		else tr[x].val=del(tr[x].ls,tr[x].val+1);
		return ans;
	}
	if(d<tr[x].val)return ans=del(tr[x].ls,d);
	else return ans=del(tr[x].rs,d);
}
inline int rank(int &x,int d)//已知权值返回第几大 
{
	if(!x)return 1;
	if(d<=tr[x].val)return rank(tr[x].ls,d);
	else return tr[tr[x].ls].sum+1+rank(tr[x].rs,d);
}
inline int select(int &x,int d)//知道第几大找权值 
{
	if(d==tr[tr[x].ls].sum+1)return tr[x].val;
	if(d<=tr[tr[x].ls].sum)return select(tr[x].ls,d);
	else return select(tr[x].rs,d-tr[tr[x].ls].sum-1);
}
inline int pre(int &x,int d)//返回值d的前驱权值； 
{
	if(!x)return d;
	if(d<=tr[x].val)return pre(tr[x].ls,d);
	else
	{
		int ans=pre(tr[x].rs,d);
		if(ans==d)return tr[x].val;
		else return ans;
	}
}
inline int suc(int &x,int d)//返回值d的后继权值； 
{
	if(!x)return d;
	if(d>=tr[x].val)return suc(tr[x].rs,d);
	else
	{
		int ans=suc(tr[x].ls,d);
		if(ans==d)return tr[x].val;
		else return ans;
	}
}
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	int n,x,y;
	tr[0].sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		switch(x)
		{
			case 1:insert(root,y);
			break;
			case 2:del(root,y);
			break;
			case 3:printf("%d\n",rank(root,y));
			break;
			case 4:printf("%d\n",select(root,y));
			break;
			case 5:printf("%d\n",pre(root,y));
			break;
			case 6:printf("%d\n",suc(root,y));
			break;
		}
	}
}