最新要闻

广告

手机

“花8亿元保护资金的古建筑被改成日式餐厅” 官方回应：启动整改违规行为，严肃查处失职渎职

“花8亿元保护资金的古建筑被改成日式餐厅” 官方回应：启动整改违规行为，严肃查处失职渎职

 华宝新能(301327)2023年半年报点评：下游去库拖累业绩表现，线下渠道快速扩张

华宝新能(301327)2023年半年报点评：下游去库拖累业绩表现，线下渠道快速扩张

家电

  1. 首页
  2. 移动通信
  3. 内容

弱势无图解FHQ-Treap 及各种乱七八糟的错误方法

来源：博客园

众所周知，FHQ-Treap是一个码量少，可区间翻转，能持久化的treap（只是常熟略大）像我这种蒟蒻，想调处有旋Treap或者Splay肯定要个114514年

以下可能以FHQ代表FHQ-Treap（逃

前置芝士

treap的节点拥有两个权值，一个是值，一个是优先级。优先级满足堆的性质，值满足二叉搜索树的性质。当两个权值相同时，treap是固定的。堆的性质以及随机的优先级可以让树深保持在\(\log n\)，确保时间复杂度；而二叉搜索树可以带来求排名，前驱，后继等操作。


(资料图片)

前置提醒

FHQ-Treap 的合并要求一个FHQ的值全部小于等于另一个，建议是确定一下哪个大，哪个小。这里以左小右大为例.

操作

1、Update

这个就是和线段树一模一样的Update，不保熟（

void Update(int pos){siz[pos]=cnt[pos]+siz[son[pos][0]]+siz[son[pos][1]]; return;}

siz即FHQ的大小，son[pos][0]代表左儿子,son[pos][1]代表右儿子

2、Split

字面意思，将一个FHQ按权值\(val\)分成小于等于和大于两个。我们将一个FHQ分成\(x\)、\(y\)两个（即根节点为\(x\)、\(y\)）本文中左（即\(x\)FHQ）一律小于右（即\(y\)FHQ）

假设我们在原FHQ的节点\(pos\)

若该点的值大于\(val\)由二叉搜索树可知该点和它的右子树节点都大于\(val\),将其置入右(y)FHQ并在左子树中寻找也大于\(val\)的子树，归入该点在\(y\)FHQ所在点的左子树中

若该点的值小于等于\(val\)由二叉搜索树可知该点和它的左子树节点都小于等于\(val\),将其置入左(x)FHQ并在右子树中寻找也小于等于\(val\)的子树，归入该点在\(x\)FHQ所在点的右子树中（可能有点绕）回溯时记得及时在该点Update以保证子树大小正确。

若\(pos\)为0，即空子树，便无法再分

void Split(int pos,int vlx,int &x,int &y){if(pos==0){x=y=0;return;}if(val[pos]<=vlx) x=pos,Split(son[pos][1],vlx,son[pos][1],y);else y=pos,Split(son[pos][0],vlx,x,son[pos][0]);Update(pos);}

3、Merge

将两个FHQ合并，要求一个FHQ的所有值都小于等于另一个。由于值都是已经有大小的，我们可以将\(x\)置入\(y\)的左子树或将\(y\)置入\(x\)的右子树但我们要使优先级满足堆的性质

再次假设我们在两个FHQ的节点\(x\)和\(y\) 这里以小根堆为例

若\(x\)的优先级大于\(y\)优先级，由堆可知\(x\)和它的子树节点的优先级都大于\(y\)的优先级,因为\(x\)的值小于等于\(y\),将其加在\(y\)的左子树下

若\(x\)的优先级小于\(y\)优先级，由堆可知\(y\)和它的子树节点的优先级都大于\(x\)的优先级,因为\(y\)的值大于\(y\),将其加在\(x\)的右子树下

这里等于的条件归在哪都无所谓

回溯时记得及时在该点Update以保证子树大小正确。

若\(x\),\(y\)有一个或多个为0，即存在空节点，直接返回另一个节点或0即可

int Merge(int x,int y){if(x==0||y==0)return x+y;if(rnd[x]>rnd[y]){son[y][0]=Merge(x,son[y][0]),Update(y); return y;}else{son[x][1]=Merge(son[x][1],y),Update(x); return x;}}

4、Get

获得排名为\(vlx\)的树本文将相同的点归在同一点，使用cnt记录其实也可当作不同的点只需修改下Get和插入这里其实和不同的BST一样若\(vlx\)小于等于左子树大小，则进入左子树若\(vlx\)大于左子树大小+该节点个数（即总个数-右子树大小），则减去左子树大小和该点的cnt，进入右子树若\(vlx\)大于左子树大小且小于等于左子树大小+该节点个数，该排名就是该节点的值，return即可

int Get(int pos,int vlx){if(vlxsiz[son[pos][0]]+cnt[pos])return Get(son[pos][1],vlx-siz[son[pos][0]]-cnt[pos]);return val[pos];}

以上的方法都是\(O(log n)\)的，每次都是进入左子树或右子树，总共不超过\(log n\)层

接下来是不用递归的功能

1、插入

要插入\(vlx\)值现将原FHQ分裂出小于等于\(vlx\)的\(x\)和大于的\(y\)再从\(x\)中分出小于等于\(vlx\)的\(x"\)和等于\(vlx\)的\(z\)若\(z\)存在，给节点\(z\)的副本数和大小都加1不存在，则新建一个\(z\)节点再按顺序Merge回去

Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(z==0) New(z,vlx);else cnt[z]++,siz[z]++;Root=Merge(Merge(x,z),y);

2、删除

说道删除，FHQ直接呵呵嗨只需按插入的方法分出\(x\)若\(z\)存在且副本数大于一，给节点\(z\)的副本数和大小都减1若副本数等于一，直接丢到垃圾桶里（若\(z\)不存在，？？？删不存在的数？？？

Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(cnt[z]>1) cnt[z]--,siz[z]--;else z=0;Root=Merge(Merge(x,z),y);

3、查排名

按\(vlx-1\)分裂出小于等于\(vlx-1\)的\(x\)FHQ答案即是\(x\)大小加1

Split(Root,vlx-1,x,y);write(siz[x]+1),pc("\n");Root=Merge(x,y);

4、查排名对应的树

调用Get即可

write(Get(Root,vlx)),pc("\n");

5、前驱

按\(vlx-1\)分裂出小于等于\(vlx-1\)的\(x\)FHQ\(x\)中的最大值及是x中排名做后的Get出\(x\)中排名为\(siz[x]\)的即可

Split(Root,vlx-1,x,y);write(Get(x,siz[x])),pc("\n");Root=Merge(x,y);

6、后继

按\(vlx\)分裂出大于\(vlx\)的\(y\)FHQ\(y\)中的最小值及是y中排名第一的Get出\(x\)中排名为1的即可

Split(Root,vlx,x,y);write(Get(y,1)),pc("\n");Root=Merge(x,y);

附上完整代码

点击查看代码
#include#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define Ts template#define Tp template#define ll long long#define RS register#define gc getchar#define pc putchar#define I inlineusing namespace std;Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}namespace WrongIO{Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!="-")c=gc();if(c=="-")opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-"0",c=gc();x*=opt;return;}Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc("0");else pc("-"),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+"0");return;}    I void writec(char c[]){int len=strlen(c);for(int i=0;ir)) c=gc();}    I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}    I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}    I void readls(string &s){char c=gc();while(c!="\n") s.push_back(c),c=gc();}    Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}} using namespace WrongIO;int val[100050],cnt[100050],rnd[100050],siz[100050],son[100050][2],ct;int n,Root;void Update(int pos){siz[pos]=cnt[pos]+siz[son[pos][0]]+siz[son[pos][1]]; return;}void New(int &id,int vlx){id=++ct;val[id]=vlx;rnd[id]=rand();siz[id]=cnt[id]=1;return;}int Merge(int x,int y){if(x==0||y==0)return x+y;if(rnd[x]>rnd[y]){son[y][0]=Merge(x,son[y][0]),Update(y); return y;}else{son[x][1]=Merge(son[x][1],y),Update(x); return x;}}void Split(int pos,int vlx,int &x,int &y){if(pos==0){x=y=0;return;}if(val[pos]<=vlx) x=pos,Split(son[pos][1],vlx,son[pos][1],y);else y=pos,Split(son[pos][0],vlx,x,son[pos][0]);Update(pos);}int Get(int pos,int vlx){if(vlxsiz[son[pos][0]]+cnt[pos])return Get(son[pos][1],vlx-siz[son[pos][0]]-cnt[pos]);return val[pos];}int main(){//fo("input5");read(n);for(int i=1;i<=n;i++){int opt,vlx,x,y,z; read(opt,vlx);if(opt==1){Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(z==0) New(z,vlx);else cnt[z]++,siz[z]++;Root=Merge(Merge(x,z),y);}if(opt==2){Split(Root,vlx,x,y);Split(x,vlx-1,x,z);if(cnt[z]>1) cnt[z]--,siz[z]--;else z=0;Root=Merge(Merge(x,z),y);}if(opt==3){Split(Root,vlx-1,x,y);write(siz[x]+1),pc("\n");Root=Merge(x,y);}if(opt==4){write(Get(Root,vlx)),pc("\n");}if(opt==5){Split(Root,vlx-1,x,y);write(Get(x,siz[x])),pc("\n");Root=Merge(x,y);}if(opt==6){Split(Root,vlx,x,y);write(Get(y,1)),pc("\n");Root=Merge(x,y);}}    return 0;}//555,卡芙卡的池子歪了一个最不想要的姬子

雄氏老方，专治各种疑难杂症

1、FHQ-Treap真的短，好多都压成了一行写，导致Merge函数，忘写返回值了（2、若将相同点合成一个点，在副本数加1的同时一定要给大小也加1，这个更新不到，减1同理3、一定要明确两个FHQ的大小关系，不然会有奇怪的事发生4、分裂中的两个分支容易写错，可能会出现死循环或导致死循环，发生MLE或TLE5、一些地方要以值-1来分裂，要注意6、Merge和Split在pos为0时记得退出7-113、留给评论区114、宇宙射线照射导致的UKE，雄氏老方也治不了（

关键词：