验证中...
开源中国 2018 年度最后一场技术盛会邀你来约~错过就要等明年啦!点此立即预约
FHQ Treap 模板
原始数据 复制代码
/*
fhq Treap by xxy学姐
核心操作
split、merge
1、split
将一个treap分裂为两个treap
分裂主要有两种:以权值k为分界点、以位置k为分界点
①以权值k作为分界点
设原来的treap根节点为root,分裂后的<=k的treap_A的根节点为x;>k的treap_B的根节点为y
当前节点指针now从root开始,在treap_A的x位置加点,treap_B的y位置加点
若now的权值<=k,那么以now为根的左子树全部包含在treap_A中
把now给x,去now的右子树,x变为x的右子树,y还是y
若now的权值>k,那么以now为分界点的右子树全部包含在treap_B中
把now给y,去now的左子树,x还是x,y变为y的左子树
②以位置k作为分界点
设原来的treap根节点为root,分裂后的前k个节点组成的treap_A的根节点为x,剩下的节点构成的treap_B的根节点为y
判断放在哪棵treap的标准改成k和子树大小的比较,原理同上
2.merge
合并以x为根的treap_A和以y为根的treap_B
*****前提:A的权值全部小于B的权值
注意在merge的过程中维护好堆和二叉搜索树的性质
若优先级x<y
维护堆的性质----------->y成为x的子节点
维护二叉搜索树的性质--->y在x的右子树
若优先级x>y
维护堆的性质----------->x成为y的子节点
维护二叉搜索树的性质--->x在y的左子树
*/
#include <ctime>
#include <cstdio>
#include <algorithm>
const int N=1e5+1;
int root,tot;
int fa[N],ch[N][2],val[N],pri[N],siz[N];
//val表示节点权值,pri表示节点的优先级,维护小根堆
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
inline int read()
{
int n=0,w=1;register char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
return n*w;
}
void update(int x)
{
siz[x]=siz[ls(x)]+siz[rs(x)]+1;
}
int new_node(int v)
{
siz[++tot]=1;
val[tot]=v;
pri[tot]=rand();
return tot;
}
int merge(int x,int y)
{
if(!x||!y)return x+y;
if(pri[x]<pri[y])
{
rs(x)=merge(rs(x),y);
update(x);
return x;
}
else
{
ls(y)=merge(x,ls(y));
update(y);
return y;
}
}
void split(int now,int k,int &x,int &y)
{//第①种分裂
if(!now)x=y=0;
else
{
if(val[now]<=k)
{
x=now;
split(rs(now),k,rs(now),y);
}
else
{
y=now;
split(ls(now),k,x,ls(now));
}
update(now);
}
}
/*
void split(int now,int k,int &x,int &y)
{//第②种分裂
if(!now)x=y=0;
else
{
if(k<=siz[ch[now][0]])
{
y=now;
split(ch[now][0],k,x,ch[now][0]);
}
else
{
x=now;
split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
}
update(now);
}
}
*/
int get_kth(int now,int k)
{
/*查询排名为x的数:
直接查就好了啊……
每次看所在节点的左子树的大小
如果大于所求的x
往右走同时减去左子树的大小
如果小于所求的x
往左走同时--k
*/
while("nlh is handsome")
{
if(k<=siz[ls(now)])
now=ls(now);
else
{
k-=siz[ls(now)];
if(k==1)return now;
--k;
now=rs(now);
}
}
}
int main()
{
srand(time(0)+370523);
int n,u,v,x,y,z;
n=read();
while(n--)
{
u=read(),v=read();
switch(u)
{
case 1:
//插入一个权值为v的点:把树按照v的权值split成两个(第①种分裂),再按照顺序merge回去
split(root,v,x,y);
root=merge(merge(x,new_node(v)),y);
break;
case 2:
/*
删除**一个**权值为v的点:
1.把树按照v的权值分成两个treap,分别为A和B;
2.然后再把A按照v-1的权值分成C和D。
3.最后把D的两个左右子树merge生成E
(merge操作相当于把左子树加到右子树上面或者把右子树加到左子树上面,也就是相当于把根节点排除了,这样就达到了删除一个节点的目的)
4.然后把E和C合并得F
5.再合并F和B
*/
/*删除**所有**权值为v的点:前面split都一样,合并的时候合并C和B两个treap即可*/
split(root,v,x,z);
split(x,v-1,x,y);
y=merge(ls(y),rs(y));
root=merge(merge(x,y),z);
break;
case 3:
/*
查询权值为v的数的排名:
1.按权值以v-1为分界点,split成两科treap A(<=v-1)和B(>=v)
2.A的大小+1即为权值v的排名
3.合并A和B
*/
split(root,v-1,x,y);
printf("%d\n",siz[x]+1);
root=merge(x,y);
break;
case 4:
//查询v的排名
printf("%d\n",val[get_kth(root,v)]);
break;
case 5:
/*
求v的前驱
1.按权值以v-1为分界点,split成两棵treap A(<=v-1)和B(>=v)
2.在A中查找A的排名最靠后的数,输出
3.合并A和B
*/
split(root,v-1,x,y);
printf("%d\n",val[get_kth(x,siz[x])]);
root=merge(x,y);
break;
case 6:
/*
求v的后继
1.按权值以v为分界点,split成两棵treap A(<=v)和B(>v)
2.在B中找最靠前的数,输出
3.合并A和B
*/
split(root,v,x,y);
printf("%d\n",val[get_kth(y,1)]);
root=merge(x,y);
}
}
return 0;
}
/*
附:
如果要对区间[l,r]执行某种操作
1.以位置r作为分界点,split成两棵treap A(前r个点)和B(位置r之后的点)
2.在A中以位置l-1为分界点,split成两棵treap C(前l-1个节点)和D(第l~第r个节点)
3.对D进行操作
注意:因为执行区间操作,增加了两个虚拟节点所有节点后移一位
4.最后别忘了合并_(:з」∠)_
*/

评论列表( 0 )

你可以在登录后,发表评论

搜索帮助