题解 | 第 k 小

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 4e5 + 5;
mt19937 rnd(time(0));
int rt, cnt, n, m, k;
struct Node {
    int v, sz, l, r, pr;
} t[N];
void upd(int x) {
    t[x].sz = t[t[x].l].sz + t[t[x].r].sz + 1;
}
pii split(int u, int v) {
    if (!u) return {0, 0};
    int x, y;
    if (t[u].v <= v) {
        x = u;
        pii tmp = split(t[u].r, v);
        y = tmp.se, t[u].r = tmp.fi;
    } else {
        y = u;
        pii tmp = split(t[u].l, v);
        x = tmp.fi, t[u].l = tmp.se;
    }
    upd(u);
    return {x, y};
}
int merge(int x, int y) {
    if (!x || !y) return x | y;
    int ans;
    if (t[x].pr <= t[y].pr) {
        t[x].r = merge(t[x].r, y);
        ans = x, upd(x);
    } else {
        t[y].l = merge(x, t[y].l);
        ans = y, upd(y);
    }
    return ans;
}
int crt(int v) {
    t[++cnt].sz = 1, t[cnt].pr = rnd(), t[cnt].v = v;
    return cnt;
}
void ins(int v) {
    pii tmp = split(rt, v);
    rt = merge(merge(tmp.fi, crt(v)), tmp.se);
}
int kth(int x, int k) {
    while (true) {
        if (k <= t[t[x].l].sz)
            x = t[x].l;
        else if (k == t[t[x].l].sz + 1)
            return x;
        else {
            k -= (t[t[x].l].sz + 1);
            x = t[x].r;
        }
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1, x; i <= n; i++) cin >> x, ins(x);
    for (int op, x; m; m--) {
        cin >> op;
        if (op == 1)
            cin >> x, ins(x), n++;
        else
            cout << (n >= k ? t[kth(rt, k)].v : -1) << "\n";
    }
    return 0;
}