Code

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 3e5 + 2;
const int M = 5e4 + 2;

int n, m, s;
int tr[N << 2], pos[N], a[N], ans[M];

struct Que {
	int l, r, k, id;

	bool operator<(const Que &b) const {
		return pos[l] == pos[b.l] ? r < b.r : l < b.l;
	}
};

struct Num {
	int v, id;

	bool operator<(const Num &b) const {
		return v < b.v;
	}
};

Que q[M];
Num nm[N];

void pushup(const int &rt) {
	tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}

void update(const int &k, const int &c, const int &l, const int &r, const int &rt) {
	if (l == k && r == k) {
		tr[rt] += c;
		return;
	}
	tr[rt] += c;
	int mid = (l + r) >> 1;
	if (k <= mid) {
		update(k, c, l, mid, rt << 1);
	} else {
		update(k, c, mid + 1, r, rt << 1 | 1);
	}
	pushup(rt);
}

int query(const int &k, const int &l, const int &r, const int &rt) {
	if (l == r) {
		return l;
	}
	int mid = (l + r) >> 1;
	if (tr[rt << 1] >= k) {
		return query(k, l, mid, rt << 1);
	} else {
		return query(k - tr[rt << 1], mid + 1, r, rt << 1 | 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	s = (int) (sqrt(n));

	for (int i = 1; i <= n; ++i) {
		cin >> nm[i].v;
		nm[i].id = i;
		pos[i] = (i - 1) / s + 1;
	}
	sort(nm, nm + n + 1);
	for (int i = 1; i <= n; ++i) {
		a[nm[i].id] = 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);

	for (int i = 1, l = 1, r = 0; i <= m; ++i) {
		while (r < q[i].r) update(a[++r], 1, 1, n, 1);
		while (r > q[i].r) update(a[r--], -1, 1, n, 1);
		while (l < q[i].l) update(a[l++], -1, 1, n, 1);
		while (l > q[i].l) update(a[--l], 1, 1, n, 1);
		ans[q[i].id] = nm[query(q[i].k, 1, n, 1)].v;
	}

	for (int i = 1; i <= m; ++i) {
		cout << ans[i] << endl;
	}
	return 0;
}