https://www.luogu.com.cn/problem/P3834

给一个l，r,tree[r].sum-tree[l-1].sum就是这个区间的数的个数

const int N = 200010;
int a[N], b[N];
struct Tree
{
    int ls, rs;
#define ls(id) tree[id].ls
#define rs(id) tree[id].rs
    int sum;
}tree[N*40];
int root[N], idx;
void build(int& id, int l, int r)
{
    id = ++idx;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(ls(id), l, mid);
    build(rs(id), mid + 1, r);
}
void add(int x, int& y, int l, int r, int v)
{
    y = ++idx;
    tree[y] = tree[x];
    tree[y].sum++;
    if (l == r) return;
    int mid = (l + r) / 2;
    if (v <= mid) add(ls(x), ls(y), l, mid, v);
    else add(rs(x), rs(y), mid + 1, r, v);
}
int find(int x, int y, int l, int r, int k)
{
    if (l == r) return l;
    int mid = (l + r) / 2;
    int s = tree[ls(y)].sum - tree[ls(x)].sum;
    if (k <= s) return find(ls(x), ls(y), l, mid, k);
    else return find(rs(x), rs(y), mid + 1, r, k - s);
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - b - 1;
    build(root[0], 1, len);
    for (int i = 1; i <= n; i++)
    {
        int x = lower_bound(b + 1, b + 1 + len, a[i]) - b;
        add(root[i-1], root[i], 1, len, x);
    }
    while (m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        cout <<b[find(root[l - 1], root[r], 1, len, k)]  << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}