记录编号	248706	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.555 s
提交时间	2016-04-10 21:25:36	内存使用	2.34 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/2;
const double alpha=0.75,lga=log(1.0/alpha);
int N;
int root,tot;
class miku
{
public:
	int fa;
	int ls,rs;
	int key;
	int siz;
	miku()
	{
		ls=rs=0; 
	}
	#define fa(x) tr[x].fa
	#define ls(x) tr[x].ls
	#define rs(x) tr[x].rs
	#define key(x) tr[x].key
	#define siz(x) tr[x].siz
}tr[SIZEN];
void prepare()//和某毒瘤数据结构一样，也要放哨兵
{
	root=1;tot=2;
	key(1)=-INF;rs(1)=2;siz(1)=2;
	key(2)=INF;fa(2)=1;siz(2)=1;
}
bool balance(int x)
{
	if(alpha*siz(x)<=max(siz(ls(x)),siz(rs(x)))) return 0;
	return 1;
}
int len=0;
int lis[SIZEN];
void dfs(int x)
{
	if(ls(x)) dfs(ls(x));
	lis[++len]=x;
	if(rs(x)) dfs(rs(x));
}
int built(int l,int r)
{
	if(l>r) return 0;
	int mid=(l+r)/2,x=lis[mid];
	ls(x)=built(l,mid-1),rs(x)=built(mid+1,r);
	fa(ls(x))=x;fa(rs(x))=x;
	siz(x)=siz(ls(x))+siz(rs(x))+1;
	return x;
}
void rebuilt(int x)
{
	len=0;
	dfs(x);
	int f=fa(x);
	int l;
	if(ls(f)==x) l=0;
	else l=1;
	int y=built(1,len);
	if(l==0) ls(f)=y,fa(y)=f;
	else rs(f)=y,fa(y)=f;
	if(root==x) root=y;
}
void insert(int t)
{
	int now=root,x=++tot,dep=0;
	siz(x)=1,key(x)=t;
	while(now)
	{
		siz(now)++;
		if(t<key(now))
		{
			if(ls(now)) now=ls(now);
			else
			{
				ls(now)=x;
				fa(x)=now;
				break;
			}
		}
		else
		{
			if(rs(now)) now=rs(now);
			else 
			{
				rs(now)=x;
				fa(x)=now;
				break;
			}
		}
		dep++;
	}
	if(dep>log(tot+1.0)/lga)
	{
		int r=0;
		for(now=x;now;now=fa(now)) if(!balance(now)) r=now;
		if(r) rebuilt(r);
	}
}
int find(int t)
{
	int now=root;
	while(now)
	{
		if(key(now)==t) return now;
		else if(key(now)<t) now=rs(now);
		else now=ls(now);
	}
	return now;
}
void erase(int x)
{
	if(ls(x)&&rs(x))
	{
		int y=ls(x);
		while(rs(y)) y=rs(y);
		key(x)=key(y);
		x=y;
	}
	int son;
	if(ls(x)) son=ls(x);else son=rs(x);
	if(ls(fa(x))==x) fa(ls(fa(x))=son)=fa(x);
	else fa(rs(fa(x))=son)=fa(x);
	for(int now=x;now;now=fa(now)) siz(now)--;
	if(x==root) root=son;
}
int rank(int t)
{
	int now=root,ans=0;
	while(now)
	{
		if(key(now)<t) ans+=siz(ls(now))+1,now=rs(now);
		else now=ls(now);
	}
	return ans;
}
int getth(int k)
{
	int now=root;
	while(now)
	{
		if(siz(ls(now))+1==k) return now;
		else if(siz(ls(now))>=k) now=ls(now);
		else k-=siz(ls(now))+1,now=rs(now);
	}
	return now;
}
int low(int t)
{
	int now=root,ans=-INF;
	while(now)
	{
		if(key(now)<t) ans=max(key(now),ans),now=rs(now);
		else now=ls(now);
	}
	return ans;
}
int high(int t)
{
	int now=root,ans=INF;
	while(now)
	{
		if(key(now)>t) ans=min(ans,key(now)),now=ls(now);
		else now=rs(now);
	}
	return ans;
}
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	prepare();
	scanf("%d",&N);
	int cmd,x;
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&cmd,&x);
		//cout<<"cmd:"<<cmd<<endl;
		if(cmd==1) insert(x);
		if(cmd==2) erase(find(x));
		if(cmd==3) printf("%d\n",rank(x));
		if(cmd==4) printf("%d\n",key(getth(x+1)));
		if(cmd==5) printf("%d\n",low(x));
		if(cmd==6) printf("%d\n",high(x));
	}
	return 0;
}