昨天我重新顺了一遍 Treap 的思路，写了一篇博客（尚未发布），然后打算把板子敲一遍顺便放上去，结果……

之前写的板子是大根堆的：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e8;
int n;
struct Node {
    int l, r;
    int key, val;
    int cnt, size;
} tr[N];
int root, idx;

void push_up(int p) {  //把信息往上传递
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
    //易错点：后面加上cnt不是1
}

int get_node(int key) {
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zag(int &p) {     //左旋
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    push_up(tr[p].l), push_up(p);
}

void zig(int &p) {     //右旋
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    push_up(tr[p].r), push_up(p);
}

void build() {
    get_node(-INF); get_node(INF);  //初始化先插入两个数
    //分别为正无穷和负无穷
    root = 1; tr[1].r = 2;  
    push_up(root);
    if (tr[1].val < tr[2].val) zag(root);
}

void insert(int &p, int key) {
    if (!p) p = get_node(key);
    else if (tr[p].key == key) tr[p].cnt++;
    else if (tr[p].key > key) {    //往左子树
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val) zig(p);  //右旋调整
    } else {                     //往右子树
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val) zag(p);  //左旋调整
    }
    push_up(p);
}

void remove(int &p, int key) {
    if (!p) return;
    if (tr[p].key == key) {
        if (tr[p].cnt > 1) tr[p].cnt--;   //如果cnt大于一个则直接减去一个
        else if (tr[p].l || tr[p].r) {    //不是叶子节点
            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                //右子树是空的或左子树的val大于右子树
                zig(p);       //右旋
                remove(tr[p].r, key);  //再删除右子树
            } else {
                zag(p);       //左旋
                remove(tr[p].l, key);  //在删除左子树
            }
        } else p = 0;                     //是叶子节点则直接删除
    }
    else if (tr[p].key > key) remove(tr[p].l, key);  //在左边删
    else remove(tr[p].r, key);                       //在右边删
    push_up(p);
}

int get_rank_by_key(int p, int key) {       //通过数值找排名
    if (!p) return 0;     //在题目中不会出现的情况，但也可以特判
    if (tr[p].key == key) return tr[tr[p].l].size + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);  //往左子树找
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank) {      //通过排名找数值
    if (!p) return INF;   //不会出现的情况
    if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);  //一定在左边
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key) {             //查找严格小于key的最大数
    if (!p) return -INF;
    if (tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key) {             //查找严格大于key的最小数
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main() {
    build();
    scanf("%d", &n);
    while (n--) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);                                 //插入一个数
        else if (opt == 2) remove(root, x);                            //删除一个数
        //由于有两个哨兵，因此排名会有1的误差。
        else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);   //查询x的排名
        else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));   //查询排名为x的数
        else if (opt == 5) printf("%d\n", get_prev(root, x));          //查询x的前驱
        else printf("%d\n", get_next(root, x));          //查询x的后继
    }
    return 0;
}

然后我自己写了一遍小根堆的，发现不太对，然后我就把上面这份代码也改成小根堆的：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e8;
int n;
struct Node {
    int l, r;
    int key, val;
    int cnt, size;
} tr[N];
int root, idx;

void push_up(int p) {  //把信息往上传递
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
    //易错点：后面加上cnt不是1
}

int get_node(int key) {
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zag(int &p) {     //左旋
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    push_up(tr[p].l), push_up(p);
}

void zig(int &p) {     //右旋
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    push_up(tr[p].r), push_up(p);
}

void build() {
    get_node(-INF); get_node(INF);  //初始化先插入两个数
    //分别为正无穷和负无穷
    root = 1; tr[1].r = 2;  
    push_up(root);
    if (tr[1].val > tr[2].val) zag(root);
}

void insert(int &p, int key) {
    if (!p) p = get_node(key);
    else if (tr[p].key == key) tr[p].cnt++;
    else if (tr[p].key > key) {    //往左子树
        insert(tr[p].l, key);
        if (tr[tr[p].l].val < tr[p].val) zig(p);  //右旋调整
    } else {                     //往右子树
        insert(tr[p].r, key);
        if (tr[tr[p].r].val < tr[p].val) zag(p);  //左旋调整
    }
    push_up(p);
}

void remove(int &p, int key) {
    if (!p) return;
    if (tr[p].key == key) {
        if (tr[p].cnt > 1) tr[p].cnt--;   //如果cnt大于一个则直接减去一个
        else if (tr[p].l || tr[p].r) {    //不是叶子节点
            if (!tr[p].r || tr[tr[p].l].val < tr[tr[p].r].val) {
                //右子树是空的或左子树的val大于右子树
                zig(p);       //右旋
                remove(tr[p].r, key);  //再删除右子树
            } else {
                zag(p);       //左旋
                remove(tr[p].l, key);  //在删除左子树
            }
        } else p = 0;                     //是叶子节点则直接删除
    }
    else if (tr[p].key > key) remove(tr[p].l, key);  //在左边删
    else remove(tr[p].r, key);                       //在右边删
    push_up(p);
}

int get_rank_by_key(int p, int key) {       //通过数值找排名
    if (!p) return 0;     //在题目中不会出现的情况，但也可以特判
    if (tr[p].key == key) return tr[tr[p].l].size + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);  //往左子树找
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank) {      //通过排名找数值
    if (!p) return INF;   //不会出现的情况
    if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);  //一定在左边
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key) {             //查找严格小于key的最大数
    if (!p) return -INF;
    if (tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key) {             //查找严格大于key的最小数
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main() {
    build();
    scanf("%d", &n);
    while (n--) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);                                 //插入一个数
        else if (opt == 2) remove(root, x);                            //删除一个数
        //由于有两个哨兵，因此排名会有1的误差。
        else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);   //查询x的排名
        else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));   //查询排名为x的数
        else if (opt == 5) printf("%d\n", get_prev(root, x));          //查询x的前驱
        else printf("%d\n", get_next(root, x));          //查询x的后继
    }
    return 0;
}

结果小根堆的代码错了 7 个点，共计 11 个点。

求教为什么它错了（

另外，我自己昨天写的代码（小根堆），把 remove 函数判定是否旋转的那一行改一下符号就好了，这难道不玄学吗（

代码如下（由于是重新写的，部分变量和上面不太一样）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, INF = 0x3f3f3f3f;

int n;
struct Treap {
    int ls, rs;
    int val, prio;  //权值、随机赋值
    int cnt, sz;    //出现次数、子树大小
} tr[N];

int rt, idx = 0;

void pushup(int u) {    //统计以 u 为根子树的信息
    tr[u].sz = tr[tr[u].ls].sz + tr[tr[u].rs].sz + tr[u].cnt;   //一定不要忘记加上它自己的 cnt！
    //是加 cnt，不是加 1！因为一个元素不只出现一次！！
}

int get_node(int val) {   //新建一个节点，元素为 val，返回其编号
    tr[++idx].val = val;
    tr[idx].prio = rand();
    tr[idx].cnt = tr[idx].sz = 1;
    return idx;
}

void zag(int &u) {    //左旋
    int v = tr[u].rs;   //u 的右儿子
    tr[u].rs = tr[v].ls, tr[v].ls = u, u = v;
    pushup(tr[u].ls), pushup(u);
}

void zig(int &u) {
    int v = tr[u].ls;
    tr[u].ls = tr[v].rs, tr[v].rs = u, u = v;
    pushup(tr[u].rs), pushup(u);
}

void init() {
    get_node(-INF), get_node(INF);  //设置两个哨兵，减少查询的特判
    rt = 1; tr[1].rs = 2;   //设置两个新节点之间的关系
    if (tr[1].prio > tr[2].prio) zag(rt);   //显然要维护堆的性质
}

void insert(int &u, int val) {
    if (!u) u = get_node(val);
    else if (val == tr[u].val) tr[u].cnt++;
    else if (val < tr[u].val) {
        insert(tr[u].ls, val);
        if (tr[tr[u].ls].prio < tr[u].prio) zig(u);
    } else if (val > tr[u].val) {
        insert(tr[u].rs, val);
        if (tr[tr[u].rs].prio < tr[u].prio) zag(u);
    }
    pushup(u);
}

void remove(int &u, int val) {
    if (!u) return;
    if (val == tr[u].val) {
        if (tr[u].cnt > 1) tr[u].cnt--;
        else if (!tr[u].ls && !tr[u].rs) u = 0;
        else {
            if (!tr[u].rs || tr[tr[u].ls].prio > tr[tr[u].rs].prio) {
                zig(u);
                remove(tr[u].rs, val);
            } else {
                zag(u);
                remove(tr[u].ls, val);
            }
        }
    } else {
        if (val < tr[u].val) remove(tr[u].ls, val);
        else remove(tr[u].rs, val);
    }
    pushup(u);
}

int get_val_by_rank(int u, int rank) {  //通过排名找元素
// cout << '\t' << u << ' ' << tr[u].ls << ' ' << tr[u].rs << endl;
    if (!u) return INF;
    if (tr[tr[u].ls].sz >= rank) return get_val_by_rank(tr[u].ls, rank);
    else if (tr[tr[u].ls].sz + tr[u].cnt < rank) return get_val_by_rank(tr[u].rs, rank - tr[tr[u].ls].sz - tr[u].cnt);
    else return tr[u].val;
}

int get_rank_by_val(int u, int val) {   //通过元素找排名
    if (!u) return 0;
    if (val == tr[u].val) return tr[tr[u].ls].sz + 1;
    if (val < tr[u].val) return get_rank_by_val(tr[u].ls, val);
    return tr[tr[u].ls].sz + tr[u].cnt + get_rank_by_val(tr[u].rs, val);
}

int get_pre(int u, int val) {   //前驱
    if (!u) return -INF;
    if (val <= tr[u].val) return get_pre(tr[u].ls, val);
    return max(tr[u].val, get_pre(tr[u].rs, val));
}

int get_nxt(int u, int val) {   //后继
    if (!u) return INF;
    if (val >= tr[u].val) return get_nxt(tr[u].rs, val);
    return min(tr[u].val, get_nxt(tr[u].ls, val));
}

int main() {
    srand(time(0));
    scanf("%d", &n);
    init();
    while (n--) {
        int opt, x; scanf("%d%d", &opt, &x);
        if (opt == 1) {
            insert(rt, x);
        } else if (opt == 2) {
            remove(rt, x);
        } else if (opt == 3) {
            printf("%d\n", get_rank_by_val(rt, x) - 1); //由于有哨兵，所以会有1的误差
        } else if (opt == 4) {
            printf("%d\n", get_val_by_rank(rt, x + 1));
        } else if (opt == 5) {
            printf("%d\n", get_pre(rt, x));
        } else {
            printf("%d\n", get_nxt(rt, x));
        }
    }
    return 0;
}