rt，最后两个大数据点 WA 了。

#include<iostream>
#include<algorithm>
#define N 200000
using namespace std;

struct node {
    int sm, ls, rs;
} tr[N<<5];
int cnt, a[N], b[N], rt[N];
void build(int &u, int l, int r) {
    u = cnt++;
    if (l == r) return;
    int m = l + r >> 1;
    build(tr[u].ls, l, m), build(tr[u].rs, m+1, r);
}
int modify(int u, int l, int r, int k) {
    int v = cnt++, m = l + r >> 1; tr[v] = tr[u], tr[v].sm++;
    if (l == r) return v;
    if (k <= m) tr[v].ls = modify(tr[u].ls, l, m, k);
    else tr[v].rs = modify(tr[u].rs, m+1, r, k);
    return v;
}
int query(int u, int v, int l, int r, int k) {
    int m = l + r >> 1, t = tr[tr[v].ls].sm - tr[tr[u].ls].sm;
    if (l == r) return l;
    if (t >= k) return query(tr[u].ls, tr[v].ls, l, m, k);
    return query(tr[u].rs, tr[v].rs, m+1, r, k-t);
}
int main() {
    int n, m, q; cin >> n >> m;
    for (int i=0; i<n; i++)
        cin >> a[i], b[i] = a[i];
    sort(b, b+n), q = unique(b, b+n) - b, build(rt[0], 1, q);
    for (int i=0; i<n; i++) rt[i+1] = modify(rt[i], 1, q, lower_bound(b, b+q, a[i])-b+1);
    for (int l, r, k; m--;) cin >> l >> r >> k, cout << b[query(rt[l-1], rt[r], 1, q, k)-1] << '\n';
    return 0;
}