主席树（可持久化线段树）

#include 
using namespace std;
#define pb push_back
const int N = 2e5 + 10;
int n, m, a[N], root[N], idx;
vector  nums;
struct node{
	int l, r, cnt;
}tr[N * 4 + N * 17];
int find(int x){
	return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int build(int l, int r){
	int p = ++idx;
	if (l == r) return p;
	int mid = l + r >> 1;
	tr[p].l = build(l, mid);
	tr[p].r = build(mid + 1, r);
	return p;
}
int insert(int p, int l, int r, int x){
	int q = ++idx;
	tr[q] = tr[p];
	if (l == r){
		tr[q].cnt++;
		return q;
	}
	int mid = l + r >> 1;
	if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
	else tr[q].r = insert(tr[p].r, mid + 1, r, x);
	tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
	return q;
}
int query(int q, int p, int l, int r, int k){
	if (l == r) return r;
	int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
	int mid = l + r >> 1;
	if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
	else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		nums.pb(a[i]);
	}
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	root[0] = build(0, nums.size() - 1);
	for (int i = 1; i <= n; i++)
		root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
	while (m--){
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << "\n";
	}
	return 0;
}

洛谷模板：https://www.luogu.com.cn/problem/P3834
Acwing模板：https://www.acwing.com/problem/content/257/