参考代码：
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int cnt; int a[N],b[N],rt[N]; int tr[N<<5],ls[N<<5],rs[N<<5]; void build(int& o,int l,int r){ o=++cnt; tr[o]=0; int mid=l+r>>1; if(l==r){ return; } build(ls[o],l,mid); build(rs[o],mid+1,r); } void xg(int& o,int l,int r,int pre,int x){ o=++cnt; ls[o]=ls[pre]; rs[o]=rs[pre]; tr[o]=tr[pre]+1; int mid=l+r>>1; if(l==r) return; if(x<=mid) xg(ls[o],l,mid,ls[pre],x); if(x>mid) xg(rs[o],mid+1,r,rs[pre],x); } int cx(int u,int v,int l,int r,int k){ if(l>=r) return l; int x=tr[ls[v]]-tr[ls[u]]; int mid=l+r>>1; if(x>=k) return cx(ls[u],ls[v],l,mid,k); else return cx(rs[u],rs[v],mid+1,r,k-x); } int main(){ int n,q,m; scanf("%d %d",&n,&q); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1; build(rt[0],1,m); for(int i=1;i<=n;i++){ int t=lower_bound(b+1,b+m+1,a[i])-b; xg(rt[i],1,m,rt[i-1],t); } while(q--){ int x,y,z; scanf("%d %d %d",&x,&y,&z); int t=cx(rt[x-1],rt[y],1,m,z); printf("%d\n",b[t]); } return 0; }