```cpp
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,a[200005],le,ri,k,idx,root[200005];
vector<int> v;
struct segtree_node{
int ch[3];
int s;
}segtree[200005*22];
int getid(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void build(int l,int r,int &x){
x=++idx;
if(l==r) return;
int m=(l+r)>>1;
build(l,m,segtree[x].ch[0]);
build(m+1,r,segtree[x].ch[1]);
}
void insert(int x,int &y,int l,int r,int v){
y=++idx;
segtree[y]=segtree[x];
segtree[y].s++;
if(l==r) return;
int m=(l+r)>>1;
if(v<=m) insert(segtree[x].ch[0],segtree[y].ch[0],l,m,v);//here
else insert(segtree[x].ch[1],segtree[y].ch[1],m+1,r,v);//here
}
int query(int x,int y,int l,int r,int k){
if(l==r) return l;
int m=(l+r)>>1;
int s=segtree[segtree[y].ch[0]].s-segtree[segtree[x].ch[0]].s;
if(k<=s) return query(segtree[x].ch[0],segtree[y].ch[0],l,m,k);//here
else return query(segtree[x].ch[1],segtree[y].ch[1],m+1,r,k-s);//here
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
build(1,n,root[0]);//here
for(int i=1;i<=n;i++){
insert(root[i-1],root[i],1,n,getid(a[i]));
}
for(int i=1;i<=m;i++){
cin>>le>>ri>>k;
int id=query(root[le-1],root[ri],1,n,k)-1;
cout<<v[id]<<"\n";
}
return 0;
}
```
by Tim0509 @ 2024-04-26 18:05:45
@[Tim0509](/user/933530) 谢谢!!
by wangding @ 2024-04-26 20:26:49