平衡树合并（值域有交集）

__xzm__ · 2025-07-26 14:49:07 · 个人记录

将两棵值域有交集的 fhq-treap 进行合并。（eg. CF1146F）

核心代码（其余都是 fhq 模板）：

inline int Merge(int x, int y) {
    if (!x || !y) return x|y;
    if (z[x].key > z[y].key) swap(x, y);
    push_down(x);
    pii o = split(y, z[x].val);
    z[x].l = Merge(z[x].l, o.x);
    z[x].r = Merge(z[x].r, o.y);
    push_up(x);
    return x;
}