来自这个神仙的https://www.luogu.org/space/show?uid=56230

终于明白了Treap，不知道是因为有了足够的积累了吗？

#include
    
     typedef long long ll;using namespace std;const int MAXN = 1000000;int na;int ch[MAXN + 5][2];int val[MAXN + 5], dat[MAXN + 5];int siz[MAXN + 5], cnt[MAXN + 5];int tot, root;inline void init() {    tot = 0;    //有时候需要插入负无穷/正无穷}inline int NewNode(int v) {    val[++tot] = v, dat[tot] = rand();    siz[tot] = 1, cnt[tot] = 1;    return tot;}inline void PushUp(int id) {    siz[id] = siz[ch[id][0]] + siz[ch[id][1]] + cnt[id];}inline void Rotate(int &id, int d) {    int temp = ch[id][d ^ 1];    ch[id][d ^ 1] = ch[temp][d];    ch[temp][d] = id;    id = temp;    PushUp(ch[id][d]), PushUp(id);}inline void Insert(int &id, int v) {    if(!id)        id = NewNode(v);    else {        if(v == val[id])            ++cnt[id];        else {            int d = v < val[id] ? 0 : 1;            Insert(ch[id][d], v);            if(dat[id] < dat[ch[id][d]])                Rotate(id, d ^ 1);        }        PushUp(id);    }}void Remove(int &id, int v) {    if(!id)        return;    else {        if(v == val[id]) {            if(cnt[id] > 1) {                cnt[id]--;                PushUp(id);            } else if(ch[id][0] || ch[id][1]) {                if(!ch[id][1] || dat[ch[id][0]] > dat[ch[id][1]])                    Rotate(id, 1), Remove(ch[id][1], v);                else                    Rotate(id, 0), Remove(ch[id][0], v);                PushUp(id);            } else                id = 0;        } else {            v < val[id] ? Remove(ch[id][0], v) : Remove(ch[id][1], v);            PushUp(id);        }    }}int GetRank(int id, int v) {    if(!id)        return 0;    else {        if(v == val[id])            return siz[ch[id][0]] + 1;        else if(v < val[id])            return GetRank(ch[id][0], v);        else            return siz[ch[id][0]] + cnt[id] + GetRank(ch[id][1], v);    }}int GetValue(int id, int rk) {    if(!id)        return -1;    else {        if(rk <= siz[ch[id][0]])            return GetValue(ch[id][0], rk);        else if(rk <= siz[ch[id][0]] + cnt[id])            return val[id];        else            return GetValue(ch[id][1], rk - siz[ch[id][0]] - cnt[id]);    }}int GetPrev(int v) {    int id = root, prev = -1;    while(id) {        if(val[id] < v)            prev = val[id], id = ch[id][1];        else            id = ch[id][0];    }    return prev;}int GetNext(int v) {    int id = root, next = -1;    while(id) {        if(val[id] > v)            next = val[id], id = ch[id][0];        else            id = ch[id][1];    }    return next;}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    init();    int ops;    scanf("%d", &ops);    for(int i = 1; i <= ops; i++) {        int op, x;        scanf("%d%d", &op, &x);        if(op == 1)            Insert(root, x);        else if(op == 2)            Remove(root, x);        else if(op == 3)            printf("%d\n", GetRank(root, x));        else if(op == 4)            printf("%d\n", GetValue(root, x));        else if(op == 5)            printf("%d\n", GetPrev(x));        else if(op == 6)            printf("%d\n", GetNext(x));    }    return 0;}
    

那么就再也不需要什么对顶堆了，平衡树最多也就浪费一点空间。