80份求条

#include<bits/stdc++.h>
#define MAXN 100507
using namespace std;
int tot,n,m,sum[MAXN<<5],rt[MAXN<<5],rs[MAXN<<5],ls[MAXN<<5],a[MAXN+105],ind[MAXN+105],len;
inline int getid(register const int &x){
	return lower_bound(ind+1,ind+len+1,x)-ind;
}
inline int build(register const int &l,register const int &r){
	int root=++tot;
	if(l==r) return root;
	register int mid=(l+r)>>1;
	rt[root]=build(l,mid);
	rs[root]=build(mid+1,r);
	return root;
}
inline int update(register const int &k,register const int &l,register const int &r,register const int &root) {
  register int dir = ++tot;
  ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
  if (l == r) return dir;
  register int mid =(l+r)>>1;
  if (k <= mid) ls[dir] = update(k, l, mid, ls[dir]);
  else rs[dir] = update(k, mid + 1, r, rs[dir]);
  return dir;
}
inline int query(register const int &u,register const int &v,register const int &l,register const int &r,register const int &k) {
	register int mid = l + r >> 1,
	x = sum[ls[v]] - sum[ls[u]]; 
	if (l == r) return l;
	if (k <= x) return query(ls[u], ls[v], l, mid, k);
	else return query(rs[u], rs[v], mid + 1, r, k - x);
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(register int i(1);i<=n;i=-~i){
		cin>>a[i];
	}
	memcpy(ind, a, sizeof ind);
	sort(ind + 1, ind + n + 1);
	len = unique(ind + 1, ind + n + 1) - ind - 1;
	rt[0] = build(1, len);
	for (register int i(1);i<=n;i=-~i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
	while (m--){
		register int l,r,k;
		cin>>l>>r>>k;
		cout<<ind[query(rt[l-1], rt[r], 1, len, k)]<<'\n';
	}
}