有关 vector 的灵异事件

#include<bits/stdc++.h>
#define pb push_back
#define endl '\n'

using namespace std;

const int V = 10000000;

int n;
struct Segment{
    int ls, rs;
    int cnt;
};
vector<Segment> a;
int root;

#define mid ((L + R) >> 1)
inline int newnode(){
    int p = a.size();
    a.pb({0, 0, 0});
    return p;
}
void add(int &p, int x, int k, int L = -V, int R = V){
    if (!p) p = newnode();
    a[p].cnt += k;
    if (L == R) return;
    if (x <= mid) add(a[p].ls, x, k, L, mid);
    else add(a[p].rs, x, k, mid + 1, R);
    return;
}
int query(int p, int l, int r, int L = -V, int R = V){
    if (!p) return 0;
    if (l <= L && R <= r) return a[p].cnt;
    int res = 0;
    if (l <= mid) res += query(a[p].ls, l, r, L, mid);
    if (mid < r) res += query(a[p].rs, l, r, mid + 1, R);
    return res;
}
int kth(int p, int k, int L = -V, int R = V){
    if (L == R) return L;
    if (a[a[p].ls].cnt >= k) return kth(a[p].ls, k, L, mid);
    return kth(a[p].rs, k - a[a[p].ls].cnt, mid + 1, R);
}

int main(){
    ios:: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    a.reserve(100000000);
    a.pb({0, 0, 0});
    cin >> n;
    while (n--){
        int op, x; cin >> op >> x;
        if (op == 1) add(root, x, 1);
        else if (op == 2) add(root, x, -1);
        else if (op == 3) cout << query(root, -V, x - 1) + 1 << endl;
        else if (op == 4) cout << kth(root, x) << endl;
        else if (op == 5) cout << kth(root, query(root, -V, x - 1)) << endl;
        else cout << kth(root, query(root, -V, x) + 1) << endl;
    }
    return 0;
}