中山网站建设半江红,如何做一个漂亮的网页,软件工程师报名官网,重庆美食制作FHQ Treap 主要通过 merge\operatorname{merge}merge 和 spilt\operatorname{spilt}spilt 两个核心操作和其他辅助函数来实现。
本文用 lcxlc_xlcx 表示 xxx 的左儿子#xff0c;rcxrc_xrcx 表示 xxx 的右儿子#xff0c;datxdat_xdatx 表示 xxx 的随机优先级
me…FHQ Treap 主要通过 merge\operatorname{merge}merge 和 spilt\operatorname{spilt}spilt 两个核心操作和其他辅助函数来实现。
本文用 lcxlc_xlcx 表示 xxx 的左儿子rcxrc_xrcx 表示 xxx 的右儿子datxdat_xdatx 表示 xxx 的随机优先级
merge
merge(x,y)\operatorname{merge}(x,y)merge(x,y) 要求 xxx 所在子树中的元素均小于等于 yyy 所在子树中的元素将两棵树合并并返回合并后的根节点。实现方法
若 datxdatydat_xdat_ydatxdaty则 xxx 作为新根节点yyy 与 rcxrc_xrcx 合并后的根节点作为新的 rcxrc_xrcx。若 datx≥datydat_x \ge dat_ydatx≥daty则 yyy 作为新根节点xxx 与 lcylc_ylcy 合并后的根节点作为新的 lcylc_ylcy。若出现空节点则不需合并返回 xyxyxy 即可。
inline int merge(int x,int y){if(!x||!y)return xy;pushdown(x),pushdown(y);if(tr[x].dattr[y].dat){tr[x].rcmerge(tr[x].rc,y);pushup(x);return x;}else{tr[y].lcmerge(x,tr[y].lc);pushup(y);return y;}
}spilt
按权值分裂
spilt(u,v,x,y)\operatorname{spilt}(u,v,x,y)spilt(u,v,x,y) 表示将 uuu 中 ≤v\le v≤v 的元素合并到 xxx 中将 vvv 的元素合并到 yyy 中。由于用返回值处理比较麻烦通常通过引用实现。实现方法
若 valu≤vval_u \le vvalu≤v则 uuu 及其左子树中所有元素都 ≤v\le v≤v都应划分到 xxx 中继续分裂 rcrcrc 到 rcrcrc 和 yyy 中。若 valuvval_uvvaluv则 uuu 及其右子树中所有元素都 vvv都应划分到 yyy 中继续分裂 lclclc 到 xxx 和 lclclc 中。若 uuu 为空节点则不需要分裂令 x←0x \gets 0x←0y←0y \gets0y←0返回即可。
inline void spilt(int u,int v,int x,int y){if(!u){xy0;return;}pushdown(u);if(tr[u].valv)xu,spilt(tr[u].rc,v,tr[u].rc,y);elseyu,spilt(tr[u].lc,v,x,tr[u].lc);pushup(u);
} 按排名分裂
相同道理。
inline void spilt(int u,int k,int x,int y){if(!u){xy0;return;}pushdown(u);if(ktr[tr[u].lc].siz)yu,spilt(tr[u].lc,k,x,tr[u].lc);elsexu,spilt(tr[u].rc,k-tr[tr[u].lc].siz-1,tr[u].rc,y);pushup(u);
}例题
【模板】文艺平衡树
