没加离散化，lj分块水过了……

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int n, m, s, a[MAXN], c[MAXN], cnt[MAXN], ans[MAXN];
struct node {
	int l, r, k, id;
}q[MAXN];
bool cmp(node x, node y) {
	if(x.l / s != y.l / s) {
		return x.l / s < y.l / s;
	}
	return x.r / s < y.r / s;
}
void add(int x) {
	c[a[x]] ++;
	cnt[a[x] / s] ++;
}
void del(int x) {
	c[a[x]] --;
	cnt[a[x] / s] --;
}
int query(int x) {
	for(int i = 0; ; i ++) {
		if(x <= cnt[i]) {
			for(int j = i * s; j < (i + 1) * s; j ++) {
				if(x <= c[j]) {
					return j;
				}
				x -= c[j];
			}
		}
		x -= cnt[i];
	}
}
int main() {
	cin >> n >> m;
	s = sqrt(n);
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for(int i = 1; i <= m; i ++) {
		cin >> q[i].l >> q[i].r >> q[i].k;
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);
	int l = q[1].l, r = q[1].l - 1;
	for(int i = 1; i <= m; i ++) {
		while(l > q[i].l) {
			add(-- l);
		}
		while(l < q[i].l) {
			del(l ++);
		}
		while(r > q[i].r) {
			del(r --);
		}
		while(r < q[i].r) {
			add(++ r);
		}
		ans[q[i].id] = query(q[i].k);
	}
	for(int i = 1; i <= m; i ++) {
		cout << ans[i] << endl;
	}
	return 0;
}

提交记录