记录编号	424088	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	0.412 s
提交时间	2017-07-12 20:27:42	内存使用	0.15 MiB

#include<cstdio>
#include<algorithm>
#define r register
namespace Treap
{
    inline int rand()
    {
        static int x=23333;
        return x^=x<<13,x^=x>>17,x^=x<<5;
    }
    struct node
    {
        node *ch[2];
        int val,pri,sz;
        node(int val=0):val(val)//写外边就对了……好玄学啊……
        {
            pri=rand();
            ch[0]=ch[1]=NULL;
			sz=1;
        }
		inline void update()
		{
			sz=1;
			if(ch[0])sz+=ch[0]->sz;
			if(ch[1])sz+=ch[1]->sz;
		}
    }*root;
	inline int size(node *x)
	{
		return x?x->sz:0;
	}
	node* merge(node *a,node *b)
	{
		if(!a)return b;if(!b)return a;
		if(a->pri<b->pri)
		{
			a->ch[1]=merge(a->ch[1],b);
			a->update();
			return a;
		}
		else
		{
			b->ch[0]=merge(a,b->ch[0]);
			b->update();
			return b;
		}
	}
	typedef std::pair<node*,node*>Npair;
	Npair split(node *x,int k)
	{
		if(!x)return Npair(NULL,NULL);
		r Npair y;
		if(size(x->ch[0])>=k)
		{
			y=split(x->ch[0],k);
			x->ch[0]=y.second;
			x->update();
			y.second=x;
		}
		else
		{
			y=split(x->ch[1],k-size(x->ch[0])-1);
			x->ch[1]=y.first;
			x->update();
			y.first=x;
		}
		return y;
	}
	inline int Kth(int k)
	{
		r Npair x=split(root,k-1);
		r Npair y=split(x.second,1);
		r node *ans=y.first;
		root=merge(merge(x.first,ans),y.second);
		return ans->val;
	}
	int Rank(node *x,int k)
	{
		if(!x)return 0;
		return k<x->val?Rank(x->ch[0],k):Rank(x->ch[1],k)+size(x->ch[0])+1;
	}
	inline void Insert(int val)
	{
		r int k=Rank(root,val);
		r Npair x=split(root,k);
		r node *a=new node(val);
		root=merge(merge(x.first,a),x.second);
	}
	inline void Delete(int val)
	{
		r int k=Rank(root,val);
		r Npair x=split(root,k-1);
		r Npair y=split(x.second,1);
		r node *ans=y.first;
		root=merge(x.first,y.second);
		delete ans;
		ans=NULL;
	}
	inline int prefix(int val)
	{
		r int k=Rank(root,val-1);
		return Kth(k);
	}
	inline int suffix(int val)
	{
		r int k=Rank(root,val);
		return Kth(k+1);
	}
}
int haha()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	int n;scanf("%d",&n);
	while(n--)
	{
		r int opt,x;scanf("%d%d",&opt,&x);
		switch(opt)
		{
			case 1:Treap::Insert(x);break;
			case 2:Treap::Delete(x);break;
			case 3:printf("%d\n",Treap::Rank(Treap::root,x-1)+1);break;
			case 4:printf("%d\n",Treap::Kth(x));break;
			case 5:printf("%d\n",Treap::prefix(x));break;
			case 6:printf("%d\n",Treap::suffix(x));break;
		}
	}
}
int sb=haha();
int main(){;}