题解 | 第 k 小

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fc freopen("in.in", "r", stdin), freopen("out.out", "w", stdout)
const int N = 2e5 + 10;
int tr[N << 5], ls[N << 5], rs[N << 5];
int tot, rt;
void ins(int& u, int l, int r, int p) {
    if (!u) u = ++tot;
    if (l == r) {
        tr[u]++;
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid)
        ins(ls[u], l, mid, p);
    else
        ins(rs[u], mid + 1, r, p);
    tr[u] = tr[ls[u]] + tr[rs[u]];
}
int quek(int u, int l, int r, int k) {
    if (!u) return -1;
    if (l == r) {
        return l;
    }
    int mid = l + r >> 1;
    if (k <= tr[ls[u]]) return quek(ls[u], l, mid, k);
    return quek(rs[u], mid + 1, r, k - tr[ls[u]]);
}
void Luo_Saisei() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        ins(rt, 0, 1e9, x);
    }
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            ins(rt, 0, 1e9, x);
        } else {
            cout << quek(rt, 0, 1e9, k) << '\n';
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) Luo_Saisei();
    return 0;
}