BST 没好好学，只好写了个 Treap /kk

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, INF = 0x7fffffff;
struct Treap {
    int l, r;
    int val, dat;
    int cnt, size;
} a[N];
int tot, root, n;

template < typename T > // 快速读入
void read (T &x) {
    x = 0; bool f = 0; char ch = getchar();
    while (!isdigit (ch)) f ^= !(ch ^ 45), ch = getchar();
    while (isdigit (ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
    x = f ? x * -1 : x;
}

int New (int val) {
    a[++ tot].val = val; 
    a[tot].dat = rand();
    a[tot].cnt = a[tot].size = 1;
    return tot;
}

void upd (int p) {
    a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}

void build () {
    New (-INF); New (INF);
    root = 1; a[1].r = 2;
    upd (root);
}

void zig (int &p) {
    int q = a[p].l;
    a[p].l = a[q].r; a[q].r = p; p = q;
    upd (a[p].r); upd (p);
}

void zag (int &p) {
    int q = a[p].r;
    a[p].r = a[q].l; a[q].l = p; p = q;
    upd (a[p].l); upd (p);
}

void Insert (int &p, int val) { // 插入
    if (!p) { p = New (val); return ; }
    if (val == a[p].val) { ++ a[p].cnt; upd(p); return ; }
    if (val < a[p].val) {
        Insert (a[p].l, val);
        if (a[p].dat < a[a[p].l].dat) zig(p);
    }
    else {
        Insert (a[p].r, val);
        if (a[p].dat < a[a[p].r].dat) zag(p);
    }
    upd (p);
}

int getpre (int val) { // 前驱
    int res = 1, p = root;
    while (p) {
        if (val == a[p].val) {
            if (a[p].l > 0) {
                p = a[p].l;
                while (a[p].r > 0) p = a[p].r;
                res = p;
            }
            break;
        }
        if (a[p].val < val && a[p].val > a[res].val) res = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[res].val;
}

int getnxt (int val) { // 求后继
    int res = 2, p = root;
    while (p) {
        if (val == a[p].val) {
            if (a[p].r > 0) {
                p = a[p].r;
                while (a[p].l > 0) p = a[p].l;
                res = p;
            }
            break;
        }
        if (a[p].val > val && a[p].val < a[res].val) res = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[res].val;
}

void Remove (int &p, int val) { // 删除操作
    if (!p) return ;
    if (val == a[p].val) {
        if (a[p].cnt > 1) {
            -- a[p].cnt; upd (p);
            return ;
        }
        if (a[p].l || a[p].r) {
            if (!a[p].r || a[a[p].l].dat > a[a[p].r].dat)
                zig(p), Remove (a[p].r, val);
            else
                zag(p), Remove (a[p].l, val);
            upd (p);
        }
        else p = 0;
        return ;
    }
    val < a[p].val ? Remove (a[p].l, val) : Remove (a[p].r, val);
    upd (p);
}

int main() {
    build(); read (n);
    while (n --) {
        int opt, x; read (opt); read (x);
        switch (opt) {
            case 1: Insert (root, x); break;
            case 2: Remove (root, x); break;
            case 3: printf ("%d\n", getpre (x)); break;
            case 4: printf ("%d\n", getnxt (x)); break;
        }
    }
    // system ("pause");
    return 0;
}

宣传 pb_ds 大法（Treap 的 pb_ds）~

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
tree <LL, null_type, less<LL>, rb_tree_tag, tree_order_statistics_node_update> t;
int n; LL k, res;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int op; cin >> op >> k;
        switch (op) {
            case 1: t.insert ((k << 20) + i); break;
            case 2: t.erase (t.lower_bound (k << 20)); break;
            case 3: printf ("%lld\n", (*--t.lower_bound (k << 20)) >> 20); break;
            case 4: printf ("%lld\n",(*t.upper_bound ((k << 20) + n)) >> 20); break;
        }
    }
}

时间复杂度: $O(Tlog_2T)$