棒棒糖题 15pts 求调

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5; int a[N], root[N], c[N], b[N];
struct segtree {
	struct node { int l, r, v; } tree[N << 5];
	int cnt;
	int build(int l, int r) {
		int now = ++cnt;
		if(l == r) {
			tree[now].v = 0; 
			return now;
		} int mid = (l + r) >> 1;
		tree[now].l = build(l, mid);
		tree[now].r = build(mid+1, r);
		tree[now].v = tree[tree[now].l].v + tree[tree[now].r].v; 
		return now;
	} int update(int l, int r, int x, int d, int rt) {
		int now = ++cnt;
		tree[now].l = tree[rt].l, tree[now].r = tree[rt].r;
		tree[now].v = tree[rt].v;
		if(l == r) return tree[now].v = d, now;
		int mid = (l + r) >> 1;
		if(x <= mid) tree[now].l = update(l, mid, x, d, tree[rt].l);
		else tree[now].r = update(mid+1, r, x, d, tree[rt].r);
		tree[now].v = tree[tree[now].l].v + tree[tree[now].r].v;
		return now;
	} int query(int x, int y, int l, int r, int k) {
		if(l == r) return l;
		int mid = (l + r) >> 1;
		if((tree[tree[y].l].v - tree[tree[x].l].v) >= k)
			return query(tree[x].l, tree[y].l, l, mid, k);
		else
			return query(tree[x].r, tree[y].r, mid+1, r, k - (tree[tree[y].l].v - tree[tree[x].l].v));
	}
} seg; map<int, int> mp; int to[N];
int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n, q; cin >> n >> q;
	for(int i = 1;i <= n;i++) cin >> a[i], c[i] = a[i];
	sort(c+1, c+n+1); int cur = 0;
	for(int i = 1;i <= n;i++) 
		mp[c[i]] = (c[i] == c[i-1] ? mp[c[i-1]] : ++cur), to[cur] = c[i];
	for(int i = 1;i <= n;i++) b[mp[a[i]]]++;
	root[0] = seg.build(1, n); 
	for(int i = 1;i <= n;i++)
		root[i] = seg.update(1, n, mp[a[i]], 1, root[i-1]);
	while(q--) {
		int l, r, k; cin >> l >> r >> k;
		cout << to[seg.query(root[l-1], root[r], 1, n, k)] << endl;
	}
	return 0;
}