首先,我们需要搞懂一个概念:主席树其实是由多个线段树组成的,但构建时不需要完全建出~~
怎么理解呢,事实上,我们主席树每次构建时,并不会影响到整棵树,仅仅会对当前根节点的左孩子/右孩子造成影响
为什么我要说这些呢,因为之后各位理解代码时,此概念十分重要
然后我们回到题目上,这题求的是区间第k大,我们很容易就会联想到前缀和,由主席树
// luogu-judger-enable-o2 #include#include #include #include #include #include #define LL long long #define M 200010 using namespace std; inline LL read() { LL d=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();} return d*f; } int tot=0; int a[M],b[M]; struct Tree { int rt[M],ls[M<<5],rs[M<<5]; int val[M<<5]; void hlhs(int &t,int l,int r)//构建空树 { t=++tot; if(l==r) return; int mid=(l+r)>>1; hlhs(ls[t],l,mid); hlhs(rs[t],mid+1,r); return; } int build(int &rt,int fa,int l,int r,int po)//加入 { rt=++tot; val[rt]=val[fa]+1; if(l==r) return rt; int mid=(l+r)>>1; if(po<=mid) { rs[rt]=rs[fa]; ls[rt]=build(ls[rt],ls[fa],l,mid,po); } else { ls[rt]=ls[fa]; rs[rt]=build(rs[rt],rs[fa],mid+1,r,po); } return rt; } int q(int rt,int fa,int l,int r,int po)//询问 { int x=val[ls[fa]]-val[ls[rt]]; if(l==r) return l; int mid=(l+r)>>1; if(x>=po) return q(ls[rt],ls[fa],l,mid,po); else return q(rs[rt],rs[fa],mid+1,r,po-x); } }tree; int main() { int n=read(),m=read(); for(int i=1;i<=n;i++) b[i]=a[i]=read(); sort(b+1,b+1+n); int q=unique(b+1,b+1+n)-b-1;//去重(离散化) tree.hlhs(tree.rt[0],1,q); int p; for(int i=1;i<=n;i++) { p=lower_bound(b+1,b+q+1,a[i])-b;//求出a[i]在b中的位置,核心算法为二分查找 tree.build(tree.rt[i],tree.rt[i-1],1,q,p); } int ans,l,r,k; for(int i=1;i<=m;i++) { l=read();r=read();k=read(); ans=tree.q(tree.rt[l-1],tree.rt[r],1,q,k); printf("%d\n",b[ans]); } return 0; }