记录编号	443554	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.254 s
提交时间	2017-08-31 13:55:59	内存使用	0.31 MiB

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
struct treap
{
	int va,siz,rnum,cnt;
	treap *ls,*rs;
	treap(int va,int rnum)
	{
		this->va=va;
		this->rnum=rnum;
		cnt=1;siz=1;
		ls=rs=NULL;
	}
	int size(){
		if(this) return siz;
		return 0;
	}
}*T;
inline int get();
void insert(treap *&now,int va);
void update(treap *&now);
void turn_l(treap *&now);
void turn_r(treap *&now);
void del(treap *&now);
void del(treap *&now,int va);
inline void kth(treap *now,int va);
inline void search(treap *now,int k);
inline void pre(treap *now,int v);
inline void post(treap *now,int v);
int n,opt,x;
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	srand(time(0));
	n=get();
	for(int i=1;i<=n;i++)
	{
		opt=get();x=get();
		if(opt==1)insert(T,x);
		else if(opt==2)del(T,x);
		else if(opt==3)kth(T,x);
		else if(opt==4)search(T,x);
		else if(opt==5)pre(T,x);
		else post(T,x);
	}
	return 0;
}
inline void post(treap *now,int v)
{
	register int ans;
	while(now)
		if(now->va<=v)now=now->rs;
		else ans=now->va,now=now->ls;
	printf("%d\n",ans);
}
inline void pre(treap *now,int v)
{
	register int ans;
	while(now)
		if(now->va>=v)now=now->ls;
		else ans=now->va,now=now->rs;
	printf("%d\n",ans);
}
inline void search(treap *now,int k)
{
	register int temp;
	while(now)
	{
		temp=now->ls->size()+now->cnt;
		if(k<=now->ls->size())now=now->ls;
		else if(k<=temp)
		{
			printf("%d\n",now->va);
			return;
		}
		else now=now->rs,k-=temp;
	}
}
inline void kth(treap *now,int va)
{
	register int sum=1;
	while(now&&now->va!=va)
	{
		if(now->va<va)
		{
			sum+=now->cnt;
			if(now->ls)sum+=now->ls->siz;
			now=now->rs;
		}
		else now=now->ls;
	}
	if(now&&now->ls)sum+=now->ls->siz;
	printf("%d\n",sum);
}
void del(treap *&now,int va)
{
	if(!now)return;
	else if(now->va==va)
	{
		now->cnt--;
		now->siz--;
		if(now->cnt)return;
		del(now);
	}
	else if(now->va<va)del(now->rs,va),update(now);
	else del(now->ls,va),update(now);
}
void del(treap *&now)
{
	if(now->ls&&now->rs)
	{
		if(now->ls->rnum>now->rs->rnum)turn_r(now),del(now->rs);
		else turn_l(now),del(now->ls);
		update(now);
	}
	else 
	{
		treap *p=now;
		if(now->ls)now=now->ls;
		else now=now->rs;
		delete p;
	}
}
void turn_l(treap *&now)
{
	treap *p=now->rs;
	now->rs=p->ls;
	p->ls=now;
	update(now);update(p);
	now=p;
}
void turn_r(treap *&now)
{
	treap *p=now->ls;
	now->ls=p->rs;
	p->rs=now;
	update(now);update(p);
	now=p;
}
void update(treap *&now)
{
	now->siz=now->cnt;
	if(now->ls)now->siz+=now->ls->siz;
	if(now->rs)now->siz+=now->rs->siz;
}
void insert(treap *&now,int va)
{
	if(now==NULL)now=new treap(va,rand());
	else if(va==now->va)now->cnt++,now->siz++;
	else if(va>now->va)
	{
		insert(now->rs,va);
		if(now->rs->rnum>now->rnum)turn_l(now);
		else update(now);
	}
	else
	{
		insert(now->ls,va);
		if(now->ls->rnum>now->rnum)turn_r(now);
		else update(now);
	}
}
inline int get()
{
	int t=0,j=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}