前 $5$ 个点 AC，后 $5$ 个点 WA。

采用序列分块套值域分块的做法。

具体来说，维护前 $i$ 个块第 $j$ 个值域块的数字数量；前 $i$ 个块数字 $j$ 的数字数量。这样一段区间的块数量和就可以用前缀和得到。

每次查询就遍历一遍区间内每个值域块的数量，不断累加，找到答案应在哪一个值域块；再在值域块里面遍历数字找到答案。

对于非整块的数字，我们另维护两个序列，在查询时暴力加，查询完减回去。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, v, m, a[2000002], b[2000002], kcn, kcv, k[2000002], kv[2000002], cnt1[1002][1002], cnt2[1002][200002], nc1[1002], nc2[2000002], t[1002];
ll fd(ll x) {
	ll l = 1, r = v, res = v;
	while (l <= r) {
		ll mid = l + r >> 1;
		if (b[mid] >= x) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	return res;
}
int main() {
	cin >> n >> m;
	kcn = sqrt(n); // 序列块长 
	for (ll i = 1; i <= n; i ++ ) cin >> a[i], b[i] = a[i], k[i] = (i + kcn - 1) / kcn;
	k[n + 1] = n / kcn + 1;
	sort(b + 1, b + n + 1); // 离散化 
	v = unique(b + 1, b + n + 1) - b - 1;
	kcv = sqrt(v);
	for (ll i = 1; i <= v; i ++ ) kv[i] = (i + kcv - 1) / kcv;
	for (ll i = 1; i <= n; i ++ ) {
		a[i] = fd(a[i]);
		cnt1[k[i]][kv[a[i]]] ++; // 值域块数字个数的前缀和，以块为单位 
		cnt2[k[i]][a[i]] ++;// 每个数字个数的前缀和，以块为单位 
	}
	for (ll i = 1; i <= k[n]; i ++ ) {
		for (ll j = 1; j <= kv[v]; j ++ ) cnt1[i][j] += cnt1[i - 1][j];
		for (ll j = 1; j <= v; j ++ ) cnt2[i][j] += cnt2[i - 1][j];
	}
	for (ll l, r, x; m --; ) {
		cin >> l >> r >> x;
		if (k[l] == k[r]) { // 同一块内 
			for (ll i = l; i <= r; i ++ ) nc1[kv[a[i]]] ++, nc2[a[i]] ++;
			ll p = 0, s = 0;
			// 找到值域块 
			while (s < x) p ++, s += nc1[p];
			s -= nc1[p]; p = kcn * p - kcn;
			// 找到答案 
			while (s < x) p ++, s += nc2[p];
			cout << b[p] << "\n";
			for (ll i = l; i <= r; i ++ ) nc1[kv[a[i]]] --, nc2[a[i]] --;
		}
		else {
			for (ll i = l; k[l] == k[l - 1] && k[i] == k[l]; i ++ ) nc1[kv[a[i]]] ++, nc2[a[i]] ++;
			for (ll i = r; k[r] == k[r + 1] && k[i] == k[r]; i -- ) nc1[kv[a[i]]] ++, nc2[a[i]] ++;
			ll p = 0, s = 0, kl = k[l - 1] + 1, kr = k[r + 1] - 1;
			// 找到值域块 
			while (s < x) p ++, s += nc1[p] + (cnt1[kr][p] - cnt1[kl - 1][p]);
			s -= nc1[p] + (cnt1[kr][p] - cnt1[kl - 1][p]);
			p = kcn * p - kcn;
			// 找到答案 
			while (s < x) p ++, s += nc2[p] + (cnt2[kr][p] - cnt2[kl - 1][p]);
			cout << b[p] << "\n";
			for (ll i = l; k[l] == k[l - 1] && k[i] == k[l]; i ++ ) nc1[kv[a[i]]] --, nc2[a[i]] --;
			for (ll i = r; k[r] == k[r + 1] && k[i] == k[r]; i -- ) nc1[kv[a[i]]] --, nc2[a[i]] --;
		}
	}
}