<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入数值 $x$。
2. 删除数值 $x$(若有多个相同的数，应只删除一个)。
3. 查询数值 $x$ 的排名(若有多个相同的数，应输出最小的排名)。
4. 查询排名为 $x$ 的数值。
5. 求数值 $x$ 的前驱(前驱定义为小于 $x$ 的最大的数)。
6. 求数值 $x$ 的后继(后继定义为大于 $x$ 的最小的数)。

注意： 数据保证查询的结果一定存在。

输入格式

第一行为 $n$，表示操作的个数。

接下来 $n$ 行每行有两个数 $opt$ 和 $x$，$opt$ 表示操作的序号($1 \\le opt \\le 6$)。

输出格式

对于操作 $3,4,5,6$ 每行输出一个数，表示对应答案。

数据范围

$1 \\le n \\le 100000$,所有数均在 $\-10^7$ 到 $10^7$ 内。

输入样例：

8
1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1

输出样例：

2
20
20
20

思路

不懂$Treap$的可以看下我的分享

代码

#include <iostream>
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;
int get_node (int key) {
    tr[++idx].key = key,tr[idx].val = rand (),tr[idx].cnt = tr[idx].size = 1;
    return idx;
}
void push_up (int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
void left_rotate (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 right_rotate (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_treap () {
    get_node (-INF),get_node (INF);
    root = 1,tr[root].r = 2;
    if (tr[root].val < tr[tr[root].r].val) left_rotate (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) right_rotate (p);
    }
    else {
        insert (tr[p].r,key);
        if (tr[tr[p].r].val > tr[p].val) left_rotate (p);
    }
    push_up (p);
}
void erase (int &p,int key) {
    if (!p) return ;
    if (tr[p].key == key) {
        if (tr[p].cnt > 1) tr[p].cnt--;
        else if (tr[p].l || tr[p].r) {
            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                right_rotate (p);
                erase (tr[p].r,key);
            }
            else {
                left_rotate (p);
                erase (tr[p].l,key);
            }
        }
        else p = 0;
    }
    else if (tr[p].key > key) erase (tr[p].l,key);
    else erase (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) {
    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) {
    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_Balanced_Tree ();
    cin >> n;
    while (n--) {
        int op,x;
        cin >> op >> x;
        if (op == 1) insert (root,x);
        else if (op == 2) erase (root,x);
        else if (op == 3) cout << get_rank_by_key (root,x) - 1 << endl;
        else if (op == 4) cout << get_key_by_rank (root,x + 1) << endl;
        else if (op == 5) cout << get_prev (root,x) << endl;
        else cout << get_next (root,x) << endl;
    }
    return 0;
}