今天一天怼了平衡树。深深地被她的魅力折服了。我算是领略到了高级数据结构的美妙。oi太神奇了。
今天初识平衡树，选择了Treap。
Treap又叫树堆，是一个二叉搜索树。我们知道，它的节点插入是随机的，这样大多数情况下一个平衡的树。但是存在极其特殊的情况，就是树退化成链，这样无法支持我们期望的O(log)效率了。所以我们需要给树附加一个随机的域（里面可以理解为优先级），使树构成二叉排序树的同时，还要满足堆的性质。
Treap树建立具体解释：
我们可以使节点优先级大于儿子节点。可以让节点随机域的数值是以它为根的子树里面最小的，左右儿子都比它大，这样是不是就满足堆的性质了？hhh
至于我们要求的本身的数值，要满足二叉排序树的性质，左子树都比它小，右子树都比它大。
下面我来介绍Treap的具体操作和代码
最重要的是旋转操作，其他操作我会在代码中解释。
因为要维护堆的性质，所以要旋转。
因为要维护堆的性质，要把x旋转到node的位置。这时要满足二叉排序树的性质。Node>P>X.旋转后我们依然要满足这个性质。所以我们要让P为node的左儿子，node为X的右儿子。
代码详尽解释：
支持以下操作：
1.插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 500010
struct Treap
{
int l,r,w,v,size,rnd;
//v为实际数值；rnd为优先级；size为以它为根的子树大小；w为自身节点存的数的个数（数据可以有多个重复的数）
}tree[N];
int n;
int root,size;
void update(int k)
{
tree[k].size=tree[tree[k].l].size+tree[tree[k].r].size+tree[k].w;
//更新子树大小
}
void rturn(int &k)
{
int t=tree[k].l;
tree[k].l=tree[t].r;
tree[t].r=k;
tree[t].size=tree[k].size;
update(k);
k=t;
}//右旋转
void lturn(int &k)
{
int t=tree[k].r;
tree[k].r=tree[t].l;
tree[t].l=k;
tree[t].size=tree[k].size;
update(k);
k=t;
}//左旋转
void insert(int &k,int x)
{
if(k==0)
{
size++;
k=size;
tree[k].w=tree[k].size=1;
tree[k].v=x;
tree[k].rnd=rand();//随机数
return;
}
tree[k].size++;
if(tree[k].v==x)//如果有多个，w++
tree[k].w++;
else
{
if(tree[k].v<x)//满足二叉排序树性质
{
insert(tree[k].r,x);
if(tree[tree[k].r].rnd<tree[k].rnd)
lturn(k);//维护堆性质，左旋转
}
else
{
insert(tree[k].l,x);
if(tree[tree[k].l].rnd<tree[k].rnd)
rturn(k);
}
}
}
int tmp;
void query_pro(int k,int x)
{
if(k==0)
return;
if(x>tree[k].v)
{
tmp=k;//不断更新过程。数值小于目标值，去右子树里找 ，找到第一个比它大的值。此时更新结果即为比它小的最大的值
query_pro(tree[k].r,x);
}
else
query_pro(tree[k].l,x);
}
void query_sub(int k,int x)
{
if(k==0)
return;
if(x<tree[k].v)//与上面同理
{
tmp=k;
query_sub(tree[k].l,x);
}
else
query_sub(tree[k].r,x);
}
void del(int &k,int x)
{
if(k==0)
return;
if(tree[k].v==x)
{
if(tree[k].w>1)//若不止相同值的个数有多个，删去一个
{
tree[k].w--;
tree[k].size--;
return;
}
if(tree[k].l*tree[k].r==0)//有一个儿子为空
k=tree[k].l+tree[k].r;
else
{
if(tree[tree[k].l].rnd<tree[k].rnd)
{
rturn(k);
del(k,x);
}
else
{
lturn(k);
del(k,x);
}
}
}
else
{
if(x>tree[k].v)
{
tree[k].size--;
del(tree[k].r,x);
}
else
{
tree[k].size--;
del(tree[k].l,x);
}
}
}
int query_rank(int k,int x)
{
if(k==0)
return 0;
if(tree[k].v==x)
return tree[tree[k].l].size+1;//找到目标值，左子树都比它小，左子树大小+1即为它的排名
else
{
if(x>tree[k].v)
return tree[tree[k].l].size+tree[k].w+query_rank(tree[k].r,x);
else
return query_rank(tree[k].l,x);
}
}
int query_num(int k,int x)
{
if(k==0)
return 0;
if(x<=tree[tree[k].l].size)
return query_num(tree[k].l,x);
else
if(x>tree[tree[k].l].size+tree[k].w)
return query_num(tree[k].r,x-tree[tree[k].l].size-tree[k].w);
else
return tree[k].v;
}
int main()
{
freopen("phs.in","r",stdin);
freopen("phs.out","w",stdout);
scanf("%d",&n);
int opt,x;
pos(i,1,n)
{
scanf("%d%d",&opt,&x);
switch(opt)
{
case 1:insert(root,x);break;
case 2:del(root,x);break;
case 3:printf("%d\n",query_rank(root,x));break;
case 4:printf("%d\n",query_num(root,x));break;
case 5:tmp=0;query_pro(root,x);printf("%d\n",tree[tmp].v);break;
case 6:tmp=0;query_sub(root,x);printf("%d\n",tree[tmp].v);break;
}
}
//while(1);
return 0;
}