树状数组求条

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 5;
int n, m;
int a[MAXN];
struct FenwickTree{
	int c[MAXN];
	int lowbit(int x) {
		return x & -x;
	}
	void add(int pos, int k) {
		for (int i = pos; i <= n; i += lowbit(i)) {
			c[i] += k;
		}
	}
	ll sum(int pos) {
		ll res = 0;
		for (int i = pos; i; i -= lowbit(i)) {
			res += c[i];
		}
		return res;
	}
	ll query(int l, int r) {
		return sum(r) - sum(l - 1);
	}
	int kth(int k) {
		int l = 1, r = n, res = n;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (sum(mid) >= k) {
				r = mid - 1;
				res = mid;
			} else l = mid + 1;
		}
		return res;
	}
}BIT;
struct node {
	int l, r, id, k;
	bool operator < (const node &other) const {
		return l < other.l;
	}
}Q[MAXN];
struct Node {
	int val, id;
	bool operator < (const Node &other) const {
		return val < other.val;
	}
}b[MAXN];
int ans[MAXN];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> b[i].val;
		b[i].id = i;
	}
	sort(b + 1, b + n + 1);
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (i == 1 || b[i].val != b[i - 1].val) cnt++;
		a[b[i].id] = cnt;
	}
	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);
	int L = 1, R = 0;
	for (int i = 1; i <= m; i++) {
		while (L < Q[i].l) {
			BIT.add(L, -1);
			L++;
		}
		while (R < Q[i].r) {
			R++;
			BIT.add(R, 1);
		}
		ans[Q[i].id] = b[BIT.kth(Q[i].k)].val;
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}