解题关键：离线求区间第k小，主席树的经典裸题；
对主席树的理解：主席树维护的是一段序列中某个数字出现的次数，所以需要预先离散化，最好使用vector的erase和unique函数，很方便；如果求整段序列的第k小，我们会想到离散化二分和线段树的做法， 而主席树只是保存了序列的前缀和，排序之后，对序列的前缀分别做线段树，具有差分的性质，因此可以求任意区间的第k小，如果主席树维护索引，只需要求出某个数字在主席树中的位置，即为sort之后v中的索引；若要求第k大，建树时反向排序即可
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cstdlib> #include<iostream> #include<cmath> using namespace std; const int maxn=2e5+10; int root[maxn]; struct node{ int l,r,sum; }p[maxn*20]; int cnt=0; //建树从1开始建 //rt是当前节点在p数组中的坐标 int build(int l,int r){ int rt=++cnt; p[rt].sum=0; p[rt].l=p[rt].r=0; if(l==r) return rt; int mid=(l+r)>>1; p[rt].l=build(l,mid); p[rt].r=build(mid+1,r); return rt; }//开始先建一棵空树，其实可以动态开点,就是各节点均为0 int update(int l,int r,int c,int k){//update更新的是索引 int nc=++cnt; p[nc]=p[c]; p[nc].sum++; int mid=(l+r)>>1; if(l==r) return nc; if(mid>=k) p[nc].l=update(l,mid,p[c].l,k); else p[nc].r=update(mid+1,r,p[c].r,k); return nc; } int query(int l,int r,int x,int y,int k){ if(l==r) return l; int mid=(l+r)>>1; int sum=p[p[y].l].sum-p[p[x].l].sum; if(sum>=k) return query(l,mid,p[x].l,p[y].l,k); else return query(mid+1,r,p[x].r,p[y].r,k-sum); } vector<int>v; int a[maxn]; int getid(int x){ return int(lower_bound(v.begin(),v.end(),x)-v.begin())+1; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(), v.end()),v.end()); //建树过程很重要 //root[0]=build(1,v.size());//一定注意更新root数组 //或者上面这句就不需要 for(int i=1;i<=n;i++){ root[i]=update(1,n,root[i-1],getid(a[i]));//update是更新某个数出现次数的 } int c,d,q; for(int i=0;i<m;i++){ cin>>c>>d>>q; int ans=query(1,n,root[c-1],root[d],q); cout<<v[ans-1]<<endl; } return 0; }