1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6  7 const int mx=1e5+5; 8 int tree[30][mx]; 9 int sortt[mx];10 int sum[30][mx];11 12 void build(int l,int r,int c)13 {14     if (l==r) return ;15     int m=(l+r)>>1;16     int isame=m-l+1;17     int pl=l,pr=m+1;18     for (int i=l;i<m;i++)19         if (tree[c][i]<sortt[m]) isame--;20     for (int i=l;i<=r;i++){21         if (i==l) sum[c][i]=0;22         else sum[c][i]=sum[c][i-1];23         if (tree[c][i]<sortt[m]){24             tree[c+1][pl++]=tree[c][i];25             sum[c][i]++;26         }27         else if ( tree[c][i]==sortt[m]&&isame){28             isame--;29             tree[c+1][pl++]=tree[c][i];30             sum[c][i]++;31         }32         else tree[c+1][pr++]=tree[c][i];33     }34     build(l,m,c+1);35     build(m+1,r,c+1);36 }37 38 int query(int L,int R,int l,int r,int c,int k){39     if (L==R) return tree[c][L];40     int s,ss;41     if (l==L){42         s=0;43         ss=sum[c][r];44     }45     else{46         s=sum[c][l-1];47         ss=sum[c][r]-s;48     }49     int m=(L+R)>>1;50     if (k<=ss) return query(L,m,L+s,L+s+ss-1,c+1,k);51     return query(m+1,R,m+1+l-L-s,m+1+r-L-s-ss,c+1,k-ss);52 }53 54 int main(){55     int n,m;56     scanf("%d%d",&n,&m);57     for (int i=1;i<=n;i++){58         scanf("%d",&sortt[i]);59         tree[0][i]=sortt[i];60     }61     sort(sortt+1,sortt+1+n);62     build(1,n,0);63     while (m--)64     {65         int l,r,k;66         scanf("%d%d%d",&l,&r,&k);67         printf("%d\n",query(1,n,l,r,0,k));68     }69 70 }