记录编号	408393	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.300 s
提交时间	2017-05-24 16:24:46	内存使用	0.31 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
	int key,size,p;
	node *ch[2];
	node(int k):key(k),size(1),p(rand()){}
	inline void refresh(){size=ch[0]->size+ch[1]->size+1;}
}*null=new node(0),*root=null;
void insert(int,node*&);
void erase(int,node*&);
int order(int,node*);
node *kth(int,node*);
node *pred(int,node*);
node *succ(int,node*);
void rot(node*&,int);
int n;
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	srand(23333333);
	null->size=0;
	null->ch[0]=null->ch[1]=null;
	scanf("%d",&n);
	while(n--){
		int d,x;
		scanf("%d%d",&d,&x);
		if(d==1)insert(x,root);
		else if(d==2)erase(x,root);
		else if(d==3)printf("%d\n",order(x,root));
		else if(d==4)printf("%d\n",kth(x,root)->key);
		else if(d==5)printf("%d\n",pred(x,root)->key);
		else printf("%d\n",succ(x,root)->key);
	}
	return 0;
}
void insert(int x,node *&rt){
	if(rt==null){
		rt=new node(x);
		rt->ch[0]=rt->ch[1]=null;
		return;
	}
	int d=x>rt->key;
	insert(x,rt->ch[d]);
	rt->refresh();
	if(rt->ch[d]->p<rt->p)rot(rt,d^1);
}
void erase(int x,node *&rt){
	if(x==rt->key){
		if(rt->ch[0]!=null&&rt->ch[1]!=null){
			int d=rt->ch[0]->p<rt->ch[1]->p;
			rot(rt,d);
			erase(x,rt->ch[d]);
		}
		else{
			node *y=rt->ch[0]!=null?rt->ch[0]:rt->ch[1];
			delete rt;
			rt=y;
		}
	}
	else erase(x,rt->ch[x>rt->key]);
	if(rt!=null)rt->refresh();
}
int order(int x,node *rt){
	int ans=1,d;
	while(rt!=null){
		if((d=x>rt->key))ans+=rt->ch[0]->size+1;
		rt=rt->ch[d];
	}
	return ans;
}
node *kth(int k,node *rt){
	int d;
	while(rt!=null){
		if(k==rt->ch[0]->size+1)return rt;
		if((d=k>rt->ch[0]->size))k-=rt->ch[0]->size+1;
		rt=rt->ch[d];
	}
	return null;
}
node *pred(int x,node *rt){
	node *y=null;
	int d;
	while(rt!=null){
		if((d=x>rt->key))y=rt;
		rt=rt->ch[d];
	}
	return y;
}
node *succ(int x,node *rt){
	node *y=null;
	int d;
	while(rt!=null){
		if((d=x<rt->key))y=rt;
		rt=rt->ch[d^1];
	}
	return y;
}
inline void rot(node *&x,int d){
	node *y=x->ch[d^1];
	x->ch[d^1]=y->ch[d];
	y->ch[d]=x;
	x->refresh();
	(x=y)->refresh();
}