如果使用 fhq 来写这道题，这道题要用随机合并，不能在结点中存储 $priority$。

因为在多次操作 4 后很多结点的 $priority$ 都是同一个值，极端数据下时间复杂度会由 $O(\log n)$ 退化成 $O(n)$

随机合并的代码：

node *join(node *a, node *b) {
    if (a == nil) {
        return b;
    }
    if (b == nil) {
        return a;
    }
    if (rand() % (a->size + b->size) < a->size) {
        a = pushdown(a);
        a->ch[1] = join(a->ch[1], b);
        maintain(a);
        return a;
    } else {
        b = pushdown(b);
        b->ch[0] = join(a, b->ch[0]);
        maintain(b);
        return b;
    }
}

结点中不存储 $priority$ 后就不要用笛卡尔树的建树方式了，使用二叉树建树的方式即可。

---

不同于可持久化文艺平衡树，这道题合并也需要复制节点。