可持久化线段树
特点：支持查询线段树的历史版本
实现：每次修改只涉及\(log_2N\)个点,所以每次修改就先复制上一个状态，然后修改涉及到的一条链即可，时间复杂度\(O(Nlog^2N)\)（修改因为要离散化，是双log；查询单log）
注意要保留每个状态的root，左右儿子的define，线段树的赋值，查询时要先试左儿子够不够……
#include<bits/stdc++.h>
#define mid (l+r>>1)
#define ls tr[i].ch[0]
#define rs tr[i].ch[1]
#define lc tr[j].ch[0]
#define rc tr[j].ch[1]
using namespace std;
const int N=2e5+5;
struct node{
int num,ch[2];
}tr[N*20];
int n,m,a[N],rk[N],idx=0,cnt,rt[N];
inline void upd(int i,int &j,int l,int r,int k){
j=++idx; tr[j]=tr[i]; tr[j].num++;
if(l==r) return ;
if(k<=mid) upd(ls,lc,l,mid,k);
else upd(rs,rc,mid+1,r,k);
}
inline int qry(int i,int j,int l,int r,int k){
if(l==r) return l;
int s=tr[lc].num-tr[ls].num;
if(k<=s) return qry(ls,lc,l,mid,k);
else return qry(rs,rc,mid+1,r,k-s);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m; for(int i=1;i<=n;++i) cin>>a[i],rk[i]=a[i];
sort(rk+1,rk+n+1); cnt=unique(rk+1,rk+n+1)-(rk+1);
for(int i=1;i<=n;++i) upd(rt[i-1],rt[i],1,cnt,lower_bound(rk+1,rk+cnt+1,a[i])-rk);
int i,j,k;
while(m--){
cin>>i>>j>>k;
cout<<rk[qry(rt[i-1],rt[j],1,cnt,k)]<<'\n';
}
return 0;
}