非旋转 Treap 模板

题目传送门: 洛谷 P3369、LibreOJ #104、BZOJ 3224

我们需要实现一种数据结构，实现以下操作。 1. 插入 $ x $ 数； 2. 删除 $ x $ 数（若有多个相同的数，因只删除一个）； 3. 查询 $ x $ 数的排名（若有多个相同的数，因输出最小的排名）； 4. 查询排名为 $ x $ 的数； 5. 求 $ x $ 的前趋（前趋定义为小于 $ x $，且最大的数）； 6. 求 $ x $ 的后继（后继定义为大于 $ x $，且最小的数）。

很明显，我们可以使用非旋转 Treap 来做。

AC 代码:

#include <cstdio>
#include <vector>
const int _=0;

template<typename T, int MAX = 0x7fffffff, int MIN = -0x7fffffff>
class fhqTreap {
    inline static T rand() {
        static unsigned long long seed = 19260817;
        return seed = (seed * 47821 + 0x1317D1E)
    }
    T root, count;
    struct Node {
        T l, r, k, rd, size;
        Node() {}
        Node(T k) : l(0), r(0), k(k), rd(rand()), size(1) {}
    };
    std::vector<Node> node;
    void update(T const n) {
        node[n].size = (node[n].l ? node[node[n].l].size : 0) + (node[n].r ? node[node[n].r].size : 0) + 1;
    }
    void split(T const n, T const k, T &x, T &y) {
        if (!n) x = y = 0;
        else if (k <= node[n].k) {
            split(node[n].l, k, x, y);
            node[n].l = y;
            update(y = n);
        }
        else {
            split(node[n].r, k, x, y);
            node[n].r = x;
            update(x = n);
        }
    }
    T merge(T const x, T const y) {
        if (!x || !y) return x + y;
        if (node[x].rd < node[y].rd) {
            node[x].r = merge(node[x].r, y);
            return update(x), x;
        }
        else {
            node[y].l = merge(x, node[y].l); // X < NODE[Y].L!!!!!!!!!
            return update(y), y;
        }
    }
public:
    fhqTreap() { node.push_back(Node()); }
    inline void insert(T const &k) {
        T x, y;
        split(root, k, x, y);
        node.push_back(Node(k));
        root = merge(merge(x, ++count), y);

    }
    inline void remove(T const &k) {
        T x, y, z;
        split(root, k, x, z), split(z, k + 1, z, y);
        z = merge(node[z].l, node[z].r);
        root = merge(merge(x, z), y);
    }
    inline T rank(T const &k) {
        T x, y, ans;
        split(root, k, x, y);
        if (!x) return (root = merge(x, y)), 1;
        ans = node[x].size + 1;
        return (root = merge(x, y)), ans;
    }
    inline T search(T const rk, T n = -1) {
        if (n == -1) n = root;
        T rank = (node[n].l ? node[node[n].l].size : 0) + 1;
        if (rank == rk) return node[n].k;
        if (rk < rank) {
            return search(rk, node[n].l);
        }
        else {
            return search(rk - rank, node[n].r);
        }
    }
    inline T lower(T const k) {
        T x, y, t;
        split(root, k, x, y), t = x;
        if (!x) return MIN;
        while (node[t].r) t = node[t].r;
        return (root = merge(x, y)), node[t].k;
    }

    inline T upper(T const k) {
        T x, y, t;
        split(root, k + 1, x, y), t = y;
        if (!y) return MAX;
        while(node[t].l) t = node[t].l;
        return (root = merge(x, y)), node[t].k;
    }
};

int n, opt, x;
fhqTreap<int> t;
int main(int argc, char const *argv[]) {
    scanf(
    while (n--) {
        scanf(
        switch(opt) {
            case 1:
                t.insert(x);
                break;
            case 2:
                t.remove(x);
                break;
            case 3:
                printf(
                break;
            case 4:
                printf(
                break;
            case 5:
                printf(
                break;
            case 6:
                printf(
                break;
        }
    }
    return (0^_^0);
}

(由于 NOIP 不吸氧，建议使用模板参数传递最大值，然后使用静态数组版本。)