rt，代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct SegmentTree {
    int lc, rc;
    int dat;
} t[N << 2];
int tot = 0, root[N];

int n, m;
int a[N], b[N], c[N];

int build(int l, int r) {
    int p = ++tot; t[p].dat = 0;
    if (l == r) return p;
    int mid = (l + r) >> 1;
    t[p].lc = build(l, mid), t[p].rc = build(mid + 1, r);
    return p;
}

int change(int now, int l, int r, int x, int v) {
    int p = ++tot;
    t[p] = t[now];
    if (l == r) {
        t[p].dat = v;
        return p;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) t[p].lc = change(t[now].lc, l, mid, x, v);
    if (x > mid) t[p].rc = change(t[now].rc, mid + 1, r, x, v);
    t[p].dat = t[t[p].lc].dat + t[t[p].rc].dat;
    return p;
}

int ask(int p, int q, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int val = t[t[p].lc].dat - t[t[q].lc].dat;
    if (k <= val) return ask(t[p].lc, t[q].lc, l, mid, k);
    else return ask(t[p].rc, t[q].rc, mid + 1, r, k - val);
}

void pre() {
    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b, c[a[i]] = *lower_bound(b + 1, b + 1 + n, a[i]);
    // for (int i = 1; i <= n; i++) cout << a[i] << " ";
    // puts("");
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    pre();
    root[0] = build(1, n);
    for (int i = 1; i <= n; i++) root[i] = change(root[i - 1], 1, n, a[i], 1);
    while (m--) {
        int l, r, k; cin >> l >> r >> k;
        int ans = ask(root[r], root[l - 1], 1, n, k);
        cout << c[ans] << "\n";
    }
    return 0;
}

不会是离散化写错了吧/kel，小的数据能过，数据稍微大一点点就不行了