记录编号	213594	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.175 s
提交时间	2015-12-12 19:48:08	内存使用	2.58 MiB

//ScapeGoat_Tree
#define MAXN 100010UL

#define INF 0x4fffffff

#define fa(x) (tree[x].fa)
#define ls(x) (tree[x].l)
#define rs(x) (tree[x].r)
#define val(x) (tree[x].key)
#define bs(x) (tree[x].bs)

#include <cmath>
#include <cstdio>

struct SGT_Node{int fa,l,r,key,bs;};
const double Alpha=0.75,logAlpha=log(1.0/Alpha);
SGT_Node tree[MAXN];
int n,root,cnt,dfs_clock,lis[MAXN];

inline int in(){
	int x=0,c=getchar();
	bool flag=false;
	while(c<'0'||c>'9'){
		if(c=='-') flag=true;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(flag) return -x;
	return x;
}

inline bool Balanced(int p){
	return bs(p)*Alpha>=bs(ls(p))&&bs(p)*Alpha>=bs(rs(p));
}

inline int MAX(int a,int b){
	return a>b?a:b;
}

inline int MIN(int a,int b){
	return a<b?a:b;
}

void dfs(int p){
	if(ls(p)) dfs(ls(p));
	lis[++dfs_clock]=p;
	if(rs(p)) dfs(rs(p));
	return;
}

int Build(int l,int r){
	if(l>r) return 0;
	int mid=(l+r)>>1,p=lis[mid];
	fa(ls(p)=Build(l,mid-1))=p;
	fa(rs(p)=Build(mid+1,r))=p;
	bs(p)=bs(ls(p))+bs(rs(p))+1;
	return p;
}

inline void ReBuild(int p){
	dfs_clock=0;dfs(p);
	int f=fa(p),res=(rs(fa(p))==p),new_root=Build(1,dfs_clock);
	if(!res) fa(ls(f)=new_root)=f;
	else fa(rs(f)=new_root)=f;
	if(p==root) root=new_root;
	return;
}

inline int Rank(int p){
	int Ans=0,temp=root;
	while(temp){
		if(val(temp)<p) Ans+=bs(ls(temp))+1,temp=rs(temp);
		else temp=ls(temp);
	}
	return Ans;
}

inline int GetKth(int p){
	int temp=root;
	while(temp){
		if(bs(ls(temp))+1==p) return temp;
		else if(bs(ls(temp))>=p) temp=ls(temp);
		else p-=bs(ls(temp))+1,temp=rs(temp);
	}
	return temp;
}

inline int Find(int p){
	int temp=root;
	while(temp){
		if(val(temp)==p) return temp;
		else if(val(temp)<p) temp=rs(temp);
		else temp=ls(temp);
	}
	return temp;
}

inline int Pre(int p){
	int temp=root,Ans=-INF;
	while(temp){
		if(val(temp)<p) Ans=MAX(Ans,val(temp)),temp=rs(temp);
		else temp=ls(temp);
	}
	return Ans;
}

inline int Next(int p){
	int temp=root,Ans=INF;
	while(temp){
		if(val(temp)>p) Ans=MIN(Ans,val(temp)),temp=ls(temp);
		else temp=rs(temp);
	}
	return Ans;
}

inline void Delete(int p){
	if(ls(p)&&rs(p)){
		int temp=ls(p);
		while(rs(temp)) temp=rs(temp);
		val(p)=val(temp);
		p=temp;
	}
	int son=ls(p)?ls(p):rs(p),res=(rs(fa(p))==p);
	if(res) fa(rs(fa(p))=son)=fa(p);
	else fa(ls(fa(p))=son)=fa(p);
	for(int i=fa(p);i;i=fa(i)) bs(i)--;
	if(p==root) root=son;
	return;
}

inline void Insert(int p){
	int temp=root,depth=0;
	++cnt;bs(cnt)=1,val(cnt)=p;
	while(true){
		bs(temp)++;
		if(p<val(temp)){
			if(ls(temp)) temp=ls(temp);
			else{fa(ls(temp)=cnt)=temp;break;}
		}
		else{
			if(rs(temp)) temp=rs(temp);
			else{fa(rs(temp)=cnt)=temp;break;}
		}
		depth++;
	}
	if(depth>log(cnt)/logAlpha){
		int goat=0;
		for(temp=cnt;temp;temp=fa(temp)) if(!Balanced(temp)) goat=temp;
		if(goat) ReBuild(goat);
	}
	return;
}

int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	n=in();root=1,cnt=2;
	val(1)=-INF,rs(1)=2,bs(1)=2;
	val(2)=+INF,fa(2)=1,bs(2)=1;
	for(int i=1,op,p;i<=n;i++){
		op=in(),p=in();
		if(op==1) Insert(p);
		else if(op==2) Delete(Find(p));
		else if(op==3) printf("%d\n",Rank(p));
		else if(op==4) printf("%d\n",val(GetKth(p+1)));
		else if(op==5) printf("%d\n",Pre(p));
		else if(op==6) printf("%d\n",Next(p));
	}
	return 0;
}