【模板】可持久化线段树 2（主席树）

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;

const int N = 2e5 + 5;

int n, q, a[N], b[N];

int head[N], lson[N << 5], rson[N << 5], sum[N << 5], cnt;

int build(int l, int r) {
    int rt = ++cnt;
    if (l == r) return rt;
    lson[rt] = build(l, mid);
    rson[rt] = build(mid + 1, r);
    return rt;
}

int modify(int pre, int l, int r, int pos) {
    int rt = ++cnt;
    sum[rt] = sum[pre] + 1;
    lson[rt] = lson[pre]; rson[rt] = rson[pre];
    if (l == r) return rt;
    if (pos <= mid) lson[rt] = modify(lson[pre], l, mid, pos);
    else rson[rt] = modify(rson[pre], mid + 1, r, pos);
    return rt;
}

int query(int rtx, int rty, int l, int r, int k) {
    if (l == r) return l;

    int x = sum[lson[rty]] - sum[lson[rtx]];
    if (x >= k) return query(lson[rtx], lson[rty], l, mid, k);
    else return query(rson[rtx], rson[rty], mid + 1, r, k - x);
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int m = unique(b + 1, b + 1 + n) - b - 1;
    head[0] = build(1, m);
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(b + 1, b + 1 + m, a[i]) - b;
        head[i] = modify(head[i - 1], 1, m, pos);
    }
    while(q--) {
        int x, y, k; scanf("%d %d %d", &x, &y, &k);
        int t = query(head[x - 1], head[y], 1, m, k);
        printf("%d\n", b[t]);
    }
    return 0;
}