题目链接:K-th Number
题解：我们先把数组离散离散化一下，然后先不考虑L,R的区间的关系，我们有一个棵线段树sum[]保存的是第几大到第几大出现的个数，这样我们想要询问这颗线段数的第k大是多少可以在log(n)次下就找到，但是区间的不同，一颗线段树是解决不了的，那我们如何得到L,R区间的sum数组呢？。我们可以建N棵线段树，第一棵树是空树，然后第一个数过来我们再建一课线段树在原来树的基础上，加上这个数对sum数组的贡献，这样从第一个到第N个建N棵线段树建好，我们可以发现sum【】有前缀和的性质，这样我们通过第R棵树sum[]减去L-1棵树的sum[]，这样我就可以得到L,R区间的sum【】数组。然后就可以查询第K大了，。现在最关建如何建N棵线段树（这是主席树的关建所在）。直接建N棵线段树空间复杂度会直接爆炸我们可以发现，对于第i+1棵树与第i棵数相比它只会更改不超过log(N)个结点，其他结点都是相同。所以在建第i+1棵树时就可以只要重新花费log(N)节点保存新的sum[]。让后用一个root[]保存每棵树的根节点。这么一说还不太理解的可以对着代码看看。
//#include<bits/stdc++.h> #include<set> #include<cstdio> #include<iomanip> #include<iostream> #include<string> #include<cstring> #include<algorithm> #define pb push_back #define ll long long #define PI 3.14159265 //#define ls l,m,rt<<1 //#define rs m+1,r,rt<<1|1 #define eps 1e-7 typedef unsigned long long ull; const int mod=1e9+9; const ll inf=0x3f3f3f3f3f3f3f; const int maxn=1e5+5; using namespace std; int a[maxn],b[maxn],tr[maxn*20],ls[maxn*20],rs[maxn*20],sum[20*maxn],rt[maxn],t,s,n,m,tot; void built(int &o,int l,int r) { o=++tot; int m=(l+r)>>1; if(l==r)return ; sum[o]=0; built(ls[o],l,m); built(rs[o],m+1,r); } void update(int &o,int pre,int l,int r,int x) { o=++tot; ls[o]=ls[pre];rs[o]=rs[pre]; int m=(l+r)>>1; sum[o]=sum[pre]+1; //cout<<sum[o]<<endl; if(l==r)return; if(x<=m) update(ls[o],ls[pre],l,m,x); else update(rs[o],rs[pre],m+1,r,x); } int query(int r1,int r2,int l,int r,int k) { if(l==r) { return l; } int m=(l+r)>>1; int cn=sum[ls[r1]]-sum[ls[r2]]; // cout<<ls[r1]<<"*"<<ls[r2]<<" "<<l<<' '<<r<<' '<<cn<<endl; if(cn>=k) { return query(ls[r1],ls[r2],l,m,k); } else { return query(rs[r1],rs[r2],m+1,r,k-cn); } } int main() { // scanf("%d",&t); // while(t--) // { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); int sz=unique(b+1,b+1+n)-b-1; tot=0; built(rt[0],1,sz); for(int i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+sz,a[i])-b; } for(int i=1;i<=n;i++) { update(rt[i],rt[i-1],1,sz,a[i]); } while(m--) { int x,y,z; scanf("%d %d %d",&x,&y,&z); int id=query(rt[y],rt[x-1],1,sz,z); printf("%d ",b[id]); } // } return 0; }