记录编号	489428	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.510 s
提交时间	2018-03-02 13:48:34	内存使用	1.55 MiB

#include<bits/stdc++.h>
using namespace std;
const int inf=1e5+10;
const double alpha=0.75;
int n,rt,sz;
int ls[inf],rs[inf],siz[inf],val[inf];
int p[inf],cnt;
void update(int x){
	siz[x]=siz[ls[x]]+siz[rs[x]]+1;
}
int rebuild(int l,int r){
	if(l>r)return 0;
	int mid=(l+r)>>1;
	int x=p[mid];
	siz[x]=1;
	ls[x]=rebuild(l,mid-1);
	rs[x]=rebuild(mid+1,r);
	update(x);
	return x;
}
int id,f;
void insert(int &x,int y){
	if(!x){
		x=++sz;
		siz[x]=1;
		val[x]=y;
		return ;
	}
	if(y<val[x])insert(ls[x],y);
	else insert(rs[x],y);
	update(x);
	if(max(siz[ls[x]],siz[rs[x]])>alpha*siz[x])id=x;
	if(id==ls[x]||id==rs[x])f=x;
}
int rank(int x,int y){
	if(!x)return 0;
	if(y<=val[x])return rank(ls[x],y);
	else return rank(rs[x],y)+siz[ls[x]]+1;
}
int kth(int x,int y){
	if(siz[ls[x]]+1==y)return val[x];
	if(y<siz[ls[x]]+1)return kth(ls[x],y);
	else return kth(rs[x],y-siz[ls[x]]-1);
}
void dfs(int x){
	if(ls[x])dfs(ls[x]);
	p[++cnt]=x;
	if(rs[x])dfs(rs[x]);
}
void out(int x){
	if(ls[x])out(ls[x]);
	printf("%d ",val[x]);
	if(rs[x])out(rs[x]);
}
void work(int x){
	id=-1;f=0;
	insert(rt,x);
	if(id!=-1){
		cnt=0;
		int flag=-1;
		if(ls[f]==id)flag=1;
		else if(rs[f]==id)flag=0;
		dfs(id);
		int u=rebuild(1,cnt);
		if(flag==1)ls[f]=u;//这里可能会出现一种特殊情况，即id为根，但是由于先进行rebuild了导致f(错误的)的ls发生了改变，并且恰好满足ls[f]==id
		//就出错了
		else if(flag==0)rs[f]=u;
		else rt=u;//另外情况是id为根的情况
	}
}
void del(int &x,int y){
	if(val[x]==y){
		if((!ls[x])&&(!rs[x]))x=0;
		else if(!ls[x])x=rs[x];
		else if(!rs[x])x=ls[x];
		else {
			int tmp=ls[x];
			while(rs[tmp])tmp=rs[tmp];
			val[x]=val[tmp];
			del(ls[x],val[x]);
			update(x);
		}
		return ;
	}
	if(y<val[x])del(ls[x],y);
	else del(rs[x],y);
	update(x);
}
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1)work(x);
		if(opt==2)del(rt,x);
		if(opt==3)printf("%d\n",rank(rt,x)+1);
		if(opt==4)printf("%d\n",kth(rt,x));
		if(opt==5)printf("%d\n",kth(rt,rank(rt,x)));
		if(opt==6)printf("%d\n",kth(rt,rank(rt,x+1)+1));
	}
	return 0;
}