关注我，分享高质量每日一题题解~

b站同名账号分享力扣杯历届真题视频题解，也欢迎大家提出宝贵意见！

思路：模拟

• 由于题目给定的 $x$ 仅有最多 $20000$ 种可能的值，而总的查询次数不超过 $2000$ 次，所以即便我们每次查询前驱和后继时均使用线性查找，也可以在 $4 \times 10^7$ 的计算次数内完成，不会超时。
• 本题的一个方便的点是 $x$ 在连续范围 $[-10000, 10000]$ 内，即便不是，也可以通过离散化（哈希表）将其映射到一段连续的区间。每次寻找前驱则从 $[-10000, x - 1]$ 范围内从后往前查找，寻找后继则从 $[x + 1, 10000]$ 范围内从前向后查找。
• 由于题目涉及到插入删除操作，所以利用一个哈希表记录每一个数出现的次数，插入操作加一，删除操作减一。

代码（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
typedef vector<int> VI;


int main() {
    int n;
    cin >> n;
    vector<int> vis(20010);

    for(int i = 0; i < n; i++) {
        int opt, x;
        cin >> opt >> x;

        if(opt == 1) {
            vis[x + 10005]++;
        } else if(opt == 2) {
            vis[x + 10005]--;
        } else if(opt == 3) {
            while(1) {
                x--;
                if(vis[x + 10005]) {
                    cout << x << endl;
                    break;
                }
            }
        } else {
            while(1) {
                x++;
                if(vis[x + 10005]) {
                    cout << x << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

时间复杂度：$O(nC)$，其中 $C = 20000$