FHQ Treap

FHQ Treap 是非常好写的一类平衡树，平衡树的每一个节点除了携带序列元素 $\tt key$ 以外，还会额外维护 $\tt priority$ . Treap 要求 $\tt priority$ 满足小根堆（或者大跟堆）的性质，在 $\tt priority$ 随机的情况下，Treap 的大小很平衡.

节点定义

每一个节点除了携带序列元素以外，还需要记录 size（子树大小），或者其他信息（如最值等等）.

如果我们想让 Treap 仅仅管理序列本身而不要求元素有序的话，我们只需要 size 对 Treap 进行拆分合并即可；
但如果我们想让 Treap 保持元素有序的话，我们会需要使用 val 记录元素
- 或者也可以直接在 Treap 找到应该插入的位置，然后用合并、分裂解决

struct Treap {
    static constexpr int invalid = 1e9;
    struct Info {};

    struct node {
        int priority;
        int size, val;
        Info info;

        std::shared_ptr<node> l, r;
    };
    using ptr = std::shared_ptr<node>;

  private:
    std::mt19937 rand{std::random_device{}()};
};

Utilities

定义一些 push_up(), create(), destroy()

void pushup(const ptr &p) {
    p->size = 1;
    if (p->l) p->size += p->l->size;
    if (p->r) p->size += p->r->size;
    // maintain other info here
}

ptr create(int v = invalid) {
    auto p = std::make_shared<node>();
    p->l = p->r = nullptr, p->val = v, p->size = 1, p->priority = rand();
    // initialize info
    return p;
}

void destroy(ptr &p) { p = nullptr; }