一直 50 分，大佬求条

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;

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

struct per_seg_tree
{
	struct node
	{
		int ls, rs, num;
	} tr[N << 5];
	int build(int l, int r)
	{
		int p = ++cur;
		if (l == r) return p;
		int mid = (l + r) >> 1;
		tr[p].ls = build(l, mid);
		tr[p].rs = build(mid + 1, r);
		return p;
	}
	int modify(int orp, int l, int r, int pos)
	{
		int p = ++cur;
		tr[p] = {tr[orp].ls, tr[orp].rs, tr[orp].num + 1};
		if (l == r) return p;
		int mid = (l + r) >> 1;
		if (pos <= mid) tr[p].ls = modify(tr[orp].ls, l, mid, pos);
		else tr[p].rs = modify(tr[orp].rs, mid + 1, r, pos);
		return p;
	}
	int query(int u, int v, int l, int r, int k)
	{
		if (l >= r) return l;
		int tmp = tr[tr[v].ls].num - tr[tr[u].ls].num, mid = (l + r) >> 1, res = 0;
		if (k <= tmp) res = query(tr[u].ls, tr[v].ls, l, mid, k);
		else res = query(tr[u].rs, tr[v].rs, mid + 1, r, k - tmp);
		return res;
	}
} PST; 

signed main()
{
	scanf("%lld%lld", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
	int m = unique(b + 1, b + n + 1) - b - 1;
	rt[0] = PST.build(1, m);
	for (int i = 1; i <= m; i++)
	{
		int pos = lower_bound(b + 1, b + m + 1, a[i]) - b;
		rt[i] = PST.modify(rt[i - 1], 1, m, pos);
	}
	while (q--)
	{
		int l, r, k;
		scanf("%lld%lld%lld", &l, &r, &k);
		int e = PST.query(rt[l - 1], rt[r], 1, m, k);
		printf("%lld\n", b[e]);
	}
	return 0;
}