今天上午学了一下fhq treap感觉真的很好用啊qwq
- 变量名解释：
- \(size[i]\)表示以该节点为根的子树大小
- \(fix[i]\)表示随机权值
- \(val[i]\)表示该节点的值
- \(ch[i][0]\)表示该节点的左儿子
- \(ch[i][1]\)表示该节点的右儿子
- 更新操作：update
inline void update(int x)
{size[x]=1+size[ch[x][0]]+size[ch[x][1]];}
就是用自己的左右子树更新自己。
- 新建节点：new_node
inline int new_node(int x)
{
size[++cnt]=1;
val[cnt]=x;
fix[cnt]=rand();
return cnt;
}
- 分裂操作：split
inline void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0;
else
{
if(val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
else y=now,split(ch[now][0],k,x,ch[now][0]);
update(now);
}
}
x,y分别表示左右子树的根节点。
刚开始肯定是要初始化为0的。
之后因为分裂之后now这个点是在左子树里面的，所以如果val[now]<=k的话，当前点的左子树肯定要归到左子树里，但是右子树里的点不确定，递归求解右子树。
val[now]>k的话道理相似。
- 合并操作：merge
inline int merge(int A,int B)
{
if(!A||!B) return A+B;
if(fix[A]<fix[B])
{
ch[A][1]=merge(ch[A][1],B);
update(A);
return A;
}
else
{
ch[B][0]=merge(A,ch[B][0]);
update(B);
return B;
}
}
返回值是合并之后树的根节点。
我们比较他们的随机权值，如果B大，就把A的右子树和B进行合并。如果A大，就把A和B的左子树进行合并。
注意因为传入参数的时候A这棵树的权值默认是小于B的，所以顺序不要写反了qwq.......
- 求一棵树\((now)\)中排名第\(k\)个的数的节点编号：kth
inline int kth(int now,int k)
{
while(1)
{
if(k<=size[ch[now][0]]) now=ch[now][0];
else if(k==size[ch[now][0]]+1) return now;
else k-=size[ch[now][0]]+1,now=ch[now][1];
}
}
- 求k的全局排名:rnk
inline int rnk(int a)
{
split(root,a-1,x,y);
int res=size[x]+1;
root=merge(x,y);
return res;
}
- 插入节点:in
inline void in(int a)
{
split(root,a,x,y);
root=merge(merge(x,new_node(a)),y);
}
- 删除节点：del
inline void del(int a)
{
split(root,a,x,z);
split(x,a-1,x,y);
y=merge(ch[y][0],ch[y][1]);
root=merge(merge(x,y),z);
}
- 求前驱: pre
inline int pre(int a)
{
split(root,a-1,x,y);
int res=val[kth(x,size[x])];
root=merge(x,y);
return res;
}
分裂之后很明显x中都小于等于a，求前继的话就可以直接输出x中最大数了。
- 求后继： nxt
inline int nxt(int a)
{
split(root,a,x,y);
int res=val[kth(y,1)];
root=merge(x,y);
return res;
}
分裂之后y中的都大于a，所以直接输出y中的第一个就可以了qwq
最后以一个普通平衡树的模板AC代码来结尾吧。。。
代码对fhq封装了一下qwq
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<ctime>
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
namespace fhq
{
#define MAXN 500010
int x,y,z,root,cnt;
int size[MAXN],val[MAXN],ch[MAXN][2],fix[MAXN];
inline void update(int x){size[x]=1+size[ch[x][0]]+size[ch[x][1]];}
inline int new_node(int x){size[++cnt]=1;val[cnt]=x;fix[cnt]=rand();return cnt;}
inline int merge(int A,int B)
{
if(!A||!B) return A+B;
if(fix[A]<fix[B]){ch[A][1]=merge(ch[A][1],B);update(A);return A;}
else {ch[B][0]=merge(A,ch[B][0]);update(B);return B;}
}
inline void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0;
else{
if(val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
else y=now,split(ch[now][0],k,x,ch[now][0]);
update(now);
}
}
inline int kth(int now,int k){while(1){
if(k<=size[ch[now][0]]) now=ch[now][0];
else if(k==size[ch[now][0]]+1) return now;
else k-=size[ch[now][0]]+1,now=ch[now][1];}
}
inline int rnk(int a){split(root,a-1,x,y);int res=size[x]+1;root=merge(x,y); return res;}
inline void in(int a){split(root,a,x,y);root=merge(merge(x,new_node(a)),y);}
inline void del(int a){split(root,a,x,z);split(x,a-1,x,y);y=merge(ch[y][0],ch[y][1]);root=merge(merge(x,y),z);}
inline int pre(int a){split(root,a-1,x,y);int res=val[kth(x,size[x])];root=merge(x,y);return res;}
inline int nxt(int a){split(root,a,x,y);int res=val[kth(y,1)];root=merge(x,y);return res;}
}
using namespace std;
using namespace fhq;
int T,cur,p;
int main()
{
srand(time(NULL));
T=read();
while(T--)
{
p=read(),cur=read();
if(p==1) fhq::in(cur);
else if(p==2) del(cur);
else if(p==3) printf("%d\n",fhq::rnk(cur));
else if(p==4) printf("%d\n",fhq::val[kth(root,cur)]);
else if(p==5) printf("%d\n",fhq::pre(cur));
else if(p==6) printf("%d\n",fhq::nxt(cur));
}
return 0;
}
哦，对了用fhq如果rp好的话还可以过掉NOIP2017列队。。。。可以尝试一下qwq