主席树求条20pts只有#1#2AC

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
const int M = 2e7 + 10;
struct node
{
	int l, r, val;
} s[M];
int head[N], a[N], b[N], l, r, k, n, m, t;
void createnode()
{
	t++;
	s[t].l = s[t].r = s[t].val = 0;
}
void build(int l, int r, int x)
{
	if(l == r) return;
	createnode();
	s[x].l = t;
	build(l, l + r >> 1, s[x].l);
	createnode();
	s[x].r = t;
	build((l + r >> 1) + 1, r, s[x].r);
	s[x].val = s[s[x].l].val + s[s[x].r].val;
}
void update(int l, int r, int x, int v, int pos, int val)
{
	if(l == r)
	{
		s[x].val += val;
		return;
	}
	createnode();
	int mid = l + r >> 1;
	if(pos <= mid) 
	{
		s[x].l = t;
		s[x].r = s[v].r;
		update(l, mid, s[x].l, s[v].l, pos, val);
	}
	else
	{
		s[x].l = s[v].l;
		s[x].r = t;
		update(mid + 1, r, s[x].r, s[v].r, pos, val);
	}
	s[x].val = s[s[x].l].val + s[s[x].r].val;
}
int query(int l, int r, int lv, int rv, int k)
{
	if(l == r) return l;
	int mid = l + r >> 1;
	int cnt = s[s[rv].l].val - s[s[lv].l].val;
	if(cnt >= k) return query(l, l + r >> 1, s[lv].l, s[rv].l, k);
	else return query((l + r >> 1) + 1, r, s[lv].r, s[rv].r, k - cnt);
}
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	head[0] = 1;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	b[0] = -1;
	int tp = unique(b + 1, b + n + 1) - b - 1;
	build(1, tp, 1);
	for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + tp + 1, a[i]) - b;
	for(int i = 1; i <= n; i++) 
	{
		createnode();
		head[i] = t;
		update(1, tp, head[i], head[i - 1], a[i], 1);
	}
	for(int i = 1; i <= m; i++)
	{
		cin >> l >> r >> k;
		cout << b[query(1, tp, head[l - 1], head[r], k)] << endl;
	}
	return 0;
}