1 #include<cstdio> 2 #include<algorithm> 3 #include<vector> 4 using namespace std; 5 const int Nmax=1e5+6; 6 int n,m; 7 int cnt,root[Nmax],num[Nmax]; 8 int x,y,k; 9 struct Node10 {11     int l;12     int r;13     int sum;14 }; 15 Node tree[Nmax*40];16 vector<int> v;17 int getid(int x)18 {19     return lower_bound(v.begin(),v.end(),x)-v.begin()+1;20 }21 22 void update(int l,int r, int &x,int y,int pos)23 {24     tree[++cnt]=tree[y];25     tree[cnt].sum++;26     x=cnt;27     if(l==r)28         return;29     int mid=(l+r)>>1;30     if(mid>=pos)31         update(l,mid,tree[x].l,tree[y].l,pos);32     else33         update(mid+1,r,tree[x].r,tree[y].r,pos);34 }35 36 int query(int l,int r,int x,int y,int k)37 {38     if(l==r)39         return l;40     int mid=(l+r)>>1;41     int sum=tree[tree[y].l].sum-tree[tree[x].l].sum;42     if(sum>=k)43         return query(l,mid,tree[x].l,tree[y].l,k);44     else45         return query(mid+1,r,tree[x].r,tree[y].r,k-sum);46 }47 48 int main()49 {50     scanf("%d%d",&n,&m);51     for(int i=1;i<=n;i++)52     {53         scanf("%d",&num[i]);54         v.push_back(num[i]);55     }56     sort(v.begin(),v.end());57     v.erase(unique( v.begin(),v.end() ),v.end() );58     for(int i=1;i<=n;i++)59         update(1,n,root[i],root[i-1],getid(num[i]));60     for(int i=1;i<=m;i++)61     {62         scanf("%d%d%d",&x,&y,&k);63         printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);64     }65     return 0;66 }