【洛谷P3369】【模板】普通平衡树【Treap】

题目大意：

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 $x$ 数
删除 $x$ 数(若有多个相同的数，因只删除一个)
查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$ 。若有多个相同的数，因输出最小的排名)
查询排名为 $x$ 的数
求 $x$ 的前驱(前驱定义为小于 $x$ ，且最大的数)
求 $x$ 的后继(后继定义为大于 $x$ ，且最小的数)

思路：

总算学会敲 $Treap$ 的模板的啊，感觉这样下去菜的很快就要退役啊。
都上初三了才学会最基础的平衡树。
暑假也没有怎么刷题，真的是颓废了啊。

维护一棵 $BST$ ，满足任意节点的左子树中的节点全部小于这个点，右子树中的节点全部大于这个点。然后这样就可以相对简单的完成上述操作。

插入
这个直接在数中根据 $BST$ 的性质来找到这个点的位置，然后插入即可。动态开点。
删除
$Treap$ 其实就是随机旋转的 $BST$ ，那么就把要删除的点旋转到叶子节点处，然后直接删除即可。
注意对于每一个数字要记录一个 $cnt$ ，表示这个数字出现的次数。如果 $cnt>1$ 那么直接 $cnt--$ 即可，不需要删除。
查询排名
这个很简单，利用 $BST$ 的性质找到这个节点，然后利用子树的大小就可以求出排名。
查询数字
用给出的排名，到每一个节点时判断应该往左儿子走还是往右儿子走，找到这个数字输出即可。
注意查询前把排名加1，因为初始化时我们要在 $BST$ 中插入两个数 $+infty,-infty$ ，所以 $-infty$ 的排名一定是1。
查询前驱
显然，假设已经到达节点的权值为 $x$ ，查找的是 $val$ 的前驱。那么如果 $x<val$ ，那么答案一定在该节点以及该节点的右子树中，答案即为 $max(x,{y|yin rson})$ 。否则答案就在该节点的左子树内。
查询后继
其实查询后继和查询前驱基本没有什么区别，改一下就行了。

码亮远远没有我想象的那么长，原本以为有 $200+$ ，结果只打了 $156$ 行，对于我这种码风来说已经可以了。
注意为了保持 $BST$ 相对平衡，需要随机旋转 $BST$ 使得 $BST$ 深度较小。

代码：

#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100010,Inf=1e9;
int n,x,opt,root,tot;

struct Treenode
{
	int lc,rc,cnt,val,size,dat;
};

struct Treap
{
	Treenode t[N];
	
	int New(int val)
	{
		t[++tot].val=val;
		t[tot].dat=rand();
		t[tot].cnt=t[tot].size=1;
		return tot;
	}
	
	void update(int x)
	{
		t[x].size=t[t[x].lc].size+t[t[x].rc].size+t[x].cnt;
	}
	
	void build()
	{
		root=New(-Inf);
		t[1].rc=New(Inf);
		update(1);
	}
	
	void zig(int &x)
	{
		int y=t[x].lc;
		t[x].lc=t[y].rc; t[y].rc=x; x=y;
		update(t[x].rc); update(x);
	}
	
	void zag(int &x)
	{
		int y=t[x].rc;
		t[x].rc=t[y].lc; t[y].lc=x; x=y;
		update(t[x].lc); update(x);
	}
	
	void insert(int &x,int val)
	{
		if (!x)
		{
			x=New(val);
			return;
		}
		if (t[x].val==val)
		{
			t[x].cnt++;
			update(x);
			return;
		}
		if (val<t[x].val)
		{
			insert(t[x].lc,val);
			if (t[x].dat<t[t[x].lc].dat) zig(x);
		}
		else
		{
			insert(t[x].rc,val);
			if (t[x].dat<t[t[x].rc].dat) zag(x);
		}
		update(x);
	}
	
	void del(int &x,int val)
	{
		if (!x) return;
		if (t[x].val==val)
		{
			if (t[x].cnt>1)
			{
				t[x].cnt--;
				update(x);
				return;
			}
			if (t[x].lc || t[x].rc)
			{
				if (!t[x].lc || t[t[x].rc].dat>t[t[x].lc].dat)
					zag(x),del(t[x].lc,val);
				else
					zig(x),del(t[x].rc,val);
				update(x);
			}
			else x=0;
			return;
		}
		if (val<t[x].val) del(t[x].lc,val);
			else del(t[x].rc,val);
		update(x);
	}
	
	int get_rank(int x,int val)
	{
		if (!x) return 0;
		if (val==t[x].val) return t[t[x].lc].size+1;
		if (val<t[x].val) return get_rank(t[x].lc,val);
			else return get_rank(t[x].rc,val)+t[t[x].lc].size+t[x].cnt;
	}
	
	int get_val(int x,int rank)
	{
		if (!x) return Inf;
		if (t[t[x].lc].size+1<=rank && t[t[x].lc].size+t[x].cnt>=rank)
			return t[x].val;
		if (rank<=t[t[x].lc].size) return get_val(t[x].lc,rank);
			else return get_val(t[x].rc,rank-t[t[x].lc].size-t[x].cnt);
	}
	
	int pre(int x,int val)
	{
		if (!x) return -Inf;
		if (t[x].val<val) return max(t[x].val,pre(t[x].rc,val));
			else return pre(t[x].lc,val);
	}
	
	int next(int x,int val)
	{
		if (!x) return Inf;
		if (t[x].val>val) return min(t[x].val,next(t[x].lc,val));
			else return next(t[x].rc,val);
	}
}Treap;

int main()
{
	srand(time(0));
	scanf("%d",&n);
	Treap.build();
	while (n--)
	{
		scanf("%d%d",&opt,&x);
		if (opt==1) Treap.insert(root,x);
		if (opt==2) Treap.del(root,x);
		if (opt==3) printf("%d
",Treap.get_rank(root,x)-1);
		if (opt==4) printf("%d
",Treap.get_val(root,x+1));
		if (opt==5) printf("%d
",Treap.pre(root,x));
		if (opt==6) printf("%d
",Treap.next(root,x));
	}
	return 0;
}