拼树与拆树

普通的 Treap 中，需要通过 Zig / Zag 操作来完成对堆性质的维护。但在 fhq Treap 当中，我们可以直接把树拆掉，然后按堆的性质拼在一起即可。

合并

按照小根堆的性质合并即可。

inline int merge(int x, int y) {
    if (!x || !y)
        return x + y;
    if (p(x) < p(y)) {
        r(x) = merge(r(x), y);
        update(x);
        return x;
        // 这一段比较绕
    } else {
        l(y) = merge(x, l(y));
        update(y);
        return y;
    }
}

拆分

split() 操作又分 按值分离 和 按大小分离 两种；其中按大小分离用于区间翻转，此处需要按值分离。

split(now, k, &x, &y) 函数的意思即把以$now$为根的子树的所有节点，小于等于$k$的分到$x$中，大于$k$的分到$y$中。结合代码理解。

inline void split(int now, int k, int &x, int &y) {
    if (!now) {
        x = y = 0;
        return ;
    }
    if (v(now) <= k) {
        // now 在 x 当中
        x = now;
        split(r(now), k, r(now), y);
    } else {
        // now 在 y 当中
        y = now;
        split(l(now), k, x, l(now));
    }
    update(now);
    return ;
}

插入

插入一个值为$c$的点，就直接把整棵树拆成两半，把$c$接进来，然后再合并即可。足够暴力。

inline void insert(int c) {
    int x, y;
    split(root, c, x, y);
    root = merge(merge(x, new_node(c)), y);
    return ;
}

删除

直接把树拆到$c$为某个子树的根，然后把$c$的左右儿子合并起来，就把$c$删掉了。

inline void erase(int c) {
    int x, y, z;
    split(root, c, x, z);
    split(x, c - 1, x, y);
    // 这里也比较绞
    y = merge(l(y), r(y));
    root = merge(merge(x, y), z);
    return ;
}

第$k$大数

此处与普通 Treap 并无大异。

inline int kth(int now, int k) {
    while (now) {
        if (k == s(l(now)) + 1)
            return v(now);
        if (k <= s(l(now)))
            now = l(now);
        else {
            k -= s(l(now)) + 1;
            now = r(now);
        }
    }
    return 0;
}

排名

把树按照$c$为关键字拆了，然后查树的大小即可。简单粗暴。

inline int rank(int c) {
    int x, y;
    split(root, c - 1, x, y);
    int res = s(x) + 1;
    // 注意这里的严格性
    root = merge(x, y);
    return res;
}

前驱后继

把树按照$c-1$或者$c$为关键字拆掉，然后对于拆出来的某棵树查询树中最大 / 最小值即可。

inline int prefix(int c) {
    int x, y;
    split(root, c - 1, x, y);
    // 这里是 c - 1
    int res = kth(x, s(x));
    root = merge(x, y);
    return res;
}

inline int suffix(int c) {
    int x, y;
    split(root, c, x, y);
    // 这里是 c
    int res = kth(y, 1);
    root = merge(x, y);
    return res;
}

总结

fhq Treap 不仅支持所有平衡树的操作（包括区间翻转等 Splay 特性；仅在 LCT 中比 Splay 多了个$logn$，然而那和我有什么关系呢），而且常数与 Splay 接近，更重要的是简单好写、代码量少。所以还写个毛线的替罪羊树，直接 split() 然后 merge() 解决一切问题。

下面记录一个 class 封装好的 fhq Treap，考场上当然是不用封装，直接写全局函数即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;

template <typename T> class fhq_treap {
 private:
    int root, tot;
    struct BinarySearchTree {
        T val;
        int pri, size, lson, rson;
        #define v(x) tree[x].val
        #define p(x) tree[x].pri
        #define s(x) tree[x].size
        #define l(x) tree[x].lson
        #define r(x) tree[x].rson
    } tree[MAXN];
    inline void update(int now) {
        s(now) = s(l(now)) + s(r(now)) + 1;
        return ;
    }
    inline int new_node(T c) {
        v(++tot) = c;
        p(tot) = rand();
        s(tot) = 1;
        return tot;
    }
    inline int merge(int x, int y) {
        if (!x || !y)
            return x + y;
        if (p(x) < p(y)) {
            r(x) = merge(r(x), y);
            update(x);
            return x;
        } else {
            l(y) = merge(x, l(y));
            update(y);
            return y;
        }
    }
    inline void split(int now, T k, int &x, int &y) {
        if (!now) {
            x = y = 0;
            return ;
        }
        if (v(now) <= k) {
            x = now;
            split(r(now), k, r(now), y);
        } else {
            y = now;
            split(l(now), k, x, l(now));
        }
        update(now);
        return ;
    }

 public:
    fhq_treap() {
        root = 0;
        tot = 0;
    }
    inline int _root() {
        return root;
    }
    inline void insert(T c) {
        int x, y;
        split(root, c, x, y);
        root = merge(merge(x, new_node(c)), y);
        return ;
    }
    inline void erase(T c) {
        int x, y, z;
        split(root, c, x, z);
        split(x, c - 1, x, y);
        y = merge(l(y), r(y));
        root = merge(merge(x, y), z);
        return ;
    }
    inline T kth(int now, int k) {
        while (now) {
            if (k == s(l(now)) + 1)
                return v(now);
            if (k <= s(l(now)))
                now = l(now);
            else {
                k -= s(l(now)) + 1;
                now = r(now);
            }
        }
        return 0;
    }
    inline int rank(T c) {
        int x, y;
        split(root, c - 1, x, y);
        int res = s(x) + 1;
        root = merge(x, y);
        return res;
    }
    inline T prefix(T c) {
        int x, y;
        split(root, c - 1, x, y);
        T res = kth(x, s(x));
        root = merge(x, y);
        return res;
    }
    inline T suffix(T c) {
        int x, y;
        split(root, c, x, y);
        T res = kth(y, 1);
        root = merge(x, y);
        return res;
    }
};

fhq_treap<int> bst;
int n;
int res, uz;
char ch;

inline int read() {
    res = 0, uz = 1;
    ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            uz = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        res = (res << 3) + (res << 1) + ch - 48;
        ch = getchar();
    }
    return res * uz;
}

int main() {
    srand(time(0));
    n = read();
    for ( ; n; n--) {
        switch (read()) {
            case 1: {
                bst.insert(read());
                break;
            }
            case 2: {
                bst.erase(read());
                break;
            }
            case 3: {
                printf("%d\n", bst.rank(read()));
                break;
            }
            case 4: {
                printf("%d\n", bst.kth(bst._root(), read()));
                break;
            }
            case 5: {
                printf("%d\n", bst.prefix(read()));
                break;
            }
            default: {
                printf("%d\n", bst.suffix(read()));
                break;
            }
        }
    }
    return 0;
}

区间翻转

惰性翻转，然后在输出时 pushdown() 即可。结合代码感性理解。

（当然，可以认为线段树是这种方式的推广）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;

template <typename T> class fhq_treap {
 private:
    struct tree {
        T v;
        int p, s;
        bool f;
        tree *l, *r;
    };
    tree *root, *nul;
    void update(tree *now) {
        if (now == nul)
            return ;
        now->s = now->l->s + now->r->s + 1;
        return ;
    }
    tree *new_node(T c) {
        tree *_p;
        _p = (tree *) malloc(sizeof(tree));
        _p->l = _p->r = nul;
        _p->v = c;
        _p->p = rand();
        _p->s = 1;
        _p->f = false;
        return _p;
    }
    void pushdown(tree *now) {
        swap(now->l, now->r);
        if (now->l != nul)
            now->l->f ^= 1;
        if (now->r != nul)
            now->r->f ^= 1;
        now->f = 0;
        return ;
    }
    tree *merge(tree *x, tree *y) {
        if (x == nul)
            return y;
        if (y == nul)
            return x;
        if (x->p < y->p) {
            if (x->f)
                pushdown(x);
            x->r = merge(x->r, y);
            update(x);
            return x;
        } else {
            if (y->f)
                pushdown(y);
            y->l = merge(x, y->l);
            update(y);
            return y;
        }
    }
    void split(tree *now, int k, tree *&x, tree *&y) {
        if (now == nul) {
            x = y = nul;
            return ;
        }
        if (now->f)
            pushdown(now);
        if (now->l->s < k) {
            x = now;
            split(now->r, k - now->l->s - 1, now->r, y);
        } else {
            y = now;
            split(now->l, k, x, now->l);
        }
        update(now);
        return ;
    }

 public:
    fhq_treap() {
        nul = (tree *) malloc(sizeof(tree));
        nul->s = 0;
        root = nul;
    }
    tree *_root() {
        return root;
    }
    void insert(T c) {
        tree *x, *y;
        split(root, c, x, y);
        root = merge(merge(x, new_node(c)), y);
        return ;
    }
    void reverse(tree *now, int l, int r) {
        tree *x, *y, *z;
        split(now, l - 1, x, y);
        split(y, r - l + 1, y, z);
        y->f ^= 1;
        now = merge(merge(x, y), z);
        return ;
    }
    void print(tree *now) {
        if (now == nul)
            return ;
        if (now->f)
            pushdown(now);
        print(now->l);
        printf("%d ", now->v);
        print(now->r);
        return ;
    }
};

fhq_treap<int> bst;
int n, m;
int res, uz;
char ch;

inline int read() {
    res = 0, uz = 1;
    ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            uz = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        res = (res << 3) + (res << 1) + ch - 48;
        ch = getchar();
    }
    return res * uz;
}

int main() {
    srand(time(0));
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        bst.insert(i);
    for (int l, r; m; m--) {
        l = read(), r = read();
        bst.reverse(bst._root(), l, r);
    }
    bst.print(bst._root());
    return 0;
}