记录编号	464406	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.309 s
提交时间	2017-10-25 19:10:18	内存使用	0.31 MiB

# include "iostream"
# include "math.h"
# include "algorithm"
# include "stdio.h"
# include "time.h"
# include "string.h"
using namespace std;
# define ls(x) (x->ch[0])
# define rs(x) (x->ch[1])
# define size(x) ((x)?(x->sz):(0))
struct treap{
	   treap *ch[2];
	   int sz,rd,val;
	   treap(int x=0){val=x;sz=1;rd=rand();ch[0]=ch[1]=NULL;}
}*rt;
void turn(treap *&rt,int d){
	 treap *t=rt->ch[d^1];
	 rt->ch[d^1]=t->ch[d];
	 rt->sz=size(ls(rt))+size(rs(rt))+1;
     t->ch[d]=rt;
     t->sz=size(ls(t))+size(rs(t))+1;
     rt=t;
}
void insert(treap *&rt,int x){
	 if(!rt){
	 	rt=new treap(x);
	 	return;
	 }int d=x<(rt->val);
	 insert(rt->ch[d^1],x);
	 rt->sz=size(ls(rt))+size(rs(rt))+1;
	 if(rt->ch[d^1]->rd < rt->rd) turn(rt,d);
}
void del(treap *&rt,int x){
	 if(rt->val==x){
	 	if(ls(rt)&&rs(rt)){
	 	   int d=(ls(rt)->rd < rs(rt)->rd);
	 	   turn(rt,d);
	 	   del(rt->ch[d],x);
	 	}
	 	else{
	 		treap *t=NULL;
	 		if(ls(rt)) t=ls(rt);
	 		else t=rs(rt);
	 		delete rt;
	 		rt=t;
	 	}
	 }
	 else{
	 	int d=(x < rt->val);
	 	del(rt->ch[d^1],x);
	 }
	 if(rt) rt->sz=size(ls(rt))+size(rs(rt))+1;
}
int Rank(int x){
	treap *k=rt;
	int ans=0;
	while(k){
		  if(x>k->val) {ans+=size(ls(k))+1;k=rs(k);}
		  else k=ls(k);
	}return ans;
}
int kth(int k){
	treap *t=rt;
	while(t){
		  if(size(ls(t))+1==k) return t->val;
		  if(size(ls(t))+1>k) t=ls(t);
		  else{k-=size(ls(t))+1;t=rs(t);}
	}return 0;
}
int opt,x,T;
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		  scanf("%d%d",&opt,&x);switch(opt){
		  	case(1):insert(rt,x);break;
		  	case(2):del(rt,x);break;
		  	case(3):printf("%d\n",Rank(x)+1);break;
		  	case(4):printf("%d\n",kth(x));break;
		  	case(5):printf("%d\n",kth(Rank(x)));break;
		  	case(6):printf("%d\n",kth(Rank(x+1)+1));break;
		  }
	}
}