主席树求调

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,m,_n,a[N],b[N];
struct Segment_Tree{
	int cnt,rt[N];
	struct Node{
		int s,ls,rs;
	}tree[N<<6];
	#define ls(u) tree[u].ls
	#define rs(u) tree[u].rs
	inline void build(int &u,int l,int r){
		u=++cnt;
		if(l==r)return;
		int mid=l+r>>1;
		build(ls(u),l,mid);build(rs(u),mid+1,r);
	}
	inline void update(int &u,int b,int l,int r,int p){
		u=++cnt;
		ls(u)=ls(b),rs(u)=rs(b),tree[u].s=tree[b].s+1;
		if(l==r)return;
		int mid=l+r>>1;
		if(mid>=p)update(ls(u),ls(b),l,mid,p);
		else update(rs(u),rs(b),mid+1,r,p);
	}
	inline int query(int u,int v,int l,int r,int rk){
		if(l==r)return b[l];
		int mid=l+r>>1,num=tree[v].s-tree[u].s;
		if(num>=rk)return query(ls(u),ls(v),l,mid,rk);
		return query(rs(u),rs(v),mid+1,r,rk-num);
	}
}t;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	_n=unique(b+1,b+n+1)-b-1;
	t.build(t.rt[0],1,_n);
	for(int i=1;i<=n;i++){
		int tmp=lower_bound(b+1,b+_n+1,a[i])-b;
		t.update(t.rt[i],t.rt[i-1],1,_n,tmp);
	}
	while(m--){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",t.query(t.rt[l-1],t.rt[r],1,_n,k));
	}
	return 0;
}