1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define MP make_pair 6 #define PB push_back 7 typedef long long LL; 8 typedef pair<int,int> PII; 9 const double eps=1e-8; 10 const double pi=acos(-1.0); 11 const int K=2e6+7; 12 const int mod=1e9+7; 13 14 int tot,ls[K],rs[K],rt[K],sum[K]; 15 int a[K],b[K]; 16 //sum[o]记录的是该节点区间内出现的数的个数 17 //区间指的是将数离散化后的区间 18 void build(int &o,int l,int r) 19 { 20 o=++tot,sum[o]=0; 21 int mid=l+r>>1; 22 if(l!=r) 23 build(ls[o],l,mid),build(rs[o],mid+1,r); 24 } 25 void update(int &o,int l,int r,int last,int x) 26 { 27 o=++tot,sum[o]=sum[last]+1; 28 ls[o]=ls[last],rs[o]=rs[last]; 29 if(l==r) return ; 30 int mid=l+r>>1; 31 if(x<=mid) update(ls[o],l,mid,ls[last],x); 32 else update(rs[o],mid+1,r,rs[last],x); 33 } 34 int query(int lo,int ro,int l,int r,int k) 35 { 36 if(l==r) return b[l]; 37 int cnt=sum[ls[ro]]-sum[ls[lo]],mid=l+r>>1; 38 if(k<=cnt) return query(ls[lo],ls[ro],l,mid,k); 39 return query(rs[lo],rs[ro],mid+1,r,k-cnt); 40 } 41 int main(void) 42 { 43 int T;cin>>T; 44 while(T--) 45 { 46 tot=0; 47 int n,m,sz; 48 scanf("%d%d",&n,&m); 49 for(int i=1;i<=n;i++) 50 scanf("%d",a+i),b[i]=a[i]; 51 sort(b+1,b+1+n); 52 sz=unique(b+1,b+1+n)-b-1; 53 for(int i=1;i<=n;i++) 54 a[i]=lower_bound(b+1,b+1+sz,a[i])-b; 55 build(rt[0],1,sz); 56 for(int i=1;i<=n;i++) 57 update(rt[i],1,sz,rt[i-1],a[i]); 58 int l,r,k; 59 while(m--) 60 scanf("%d%d%d",&l,&r,&k),printf("%d ",query(rt[l-1],rt[r],1,sz,k)); 61 62 } 63 return 0; 64 }