1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<iostream> 7 #include<cmath> 8 using namespace std; 9 const int maxn=1e5+10;10 int root[maxn];11 struct node{12     int l,r,sum;13 }p[maxn*20];14 int cnt=0;15 //建树从1开始建16 //rt是当前节点在p数组中的坐标17 int build(int l,int r){18     int rt=++cnt;19     p[rt].sum=0;20     p[rt].l=p[rt].r=0;21     if(l==r) return rt;22     int mid=(l+r)>>1;23     p[rt].l=build(l,mid);24     p[rt].r=build(mid+1,r);25     return rt;26 }//开始先建一棵空树，其实可以动态开点,就是各节点均为027 int update(int l,int r,int c,int k){//update更新的是索引28     int nc=++cnt;29     p[nc]=p[c];30     p[nc].sum++;31     int mid=(l+r)>>1;32     if(l==r) return nc;33     if(mid>=k) p[nc].l=update(l,mid,p[c].l,k);34     else p[nc].r=update(mid+1,r,p[c].r,k);35     return nc;36 }37 38 int query(int l,int r,int x,int y,int k){39     if(l==r) return l;40     int mid=(l+r)>>1;41     int sum=p[p[y].l].sum-p[p[x].l].sum;42     if(sum>=k) return query(l,mid,p[x].l,p[y].l,k);43     else return query(mid+1,r,p[x].r,p[y].r,k-sum);44 }45 vector<int>v;46 int a[maxn];47 int getid(int x){48     return int(lower_bound(v.begin(),v.end(),x)-v.begin())+1;49 }50 int main(){51     ios::sync_with_stdio(0);52     cin.tie(0);53     cout.tie(0);54     int n,m;55     cin>>n>>m;56     for(int i=1;i<=n;i++){57         cin>>a[i];58         v.push_back(a[i]);59     }60     sort(v.begin(),v.end());61     v.erase(unique(v.begin(), v.end()),v.end());62     //建树过程很重要63     root[0]=build(1,n);//一定注意更新root数组64     for(int i=1;i<=n;i++){65         root[i]=update(1,n,root[i-1],getid(a[i]));//update是更新某个数出现次数的66     }67     int c,d,q;68     for(int i=0;i<m;i++){69         cin>>c>>d>>q;70         int ans=query(1,n,root[c-1],root[d],q);71         cout<<v[ans-1]<<endl;72     }73     return 0;74 }