题解 P3834 【【模板】可持久化线段树 1（主席树）】

以前不知道主席树是什么东西，听名字就觉得一定很难，什么可持久化啊，主席啊。。。 然后。。发现所谓的可持久化其实就是把每次的修改节点，不把原节点覆盖，而是暴力新开节点一个存下来。所以等于说是。。每次修改新建一棵树。。。 要访问历史版本的话就存一下第几次修改的根节点的编号是几，再按普通线段树做就行了。 这是道经典主席树模板题，求区间第k大。把原来的数组a先搬出来，复制到b，b排序之后去重，然后建一棵线段树。 按a的顺序，在线段树上进行修改 第i次修改之后的线段树l~r存的是l~r这几个数在原来数组的a1~ai中出现过几次。 这样当我们要查询l~r的第k大的时候，取出历史版本l-1和r，然后我们发现，将对应节点的数相减，刚刚好就是l~r内某个范围内的数的个数。所以对于一个区间l~r，我们可以每次算出在l~mid范围内的数，如果数量>=k，就往左子树走，否则就往右子树走。 不懂的话。。。图详见这个博客。。 https://blog.csdn.net/bestFy/article/details/78650360 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,q,cnt=0; int a[1010000],b[1010000]; int root[1010000]; struct node { int sum,l,r; }tr[10010000]; int build(int l,int r) { int u=++cnt,mid=(l+r)/2; if(l>=r) return u; tr[u].l=build(l,mid); tr[u].r=build(mid+1,r); return u; } int insert(int pre,int l,int r,int k) { int u=++cnt,mid=(l+r)/2; tr[u].l=tr[pre].l,tr[u].r=tr[pre].r,tr[u].sum=tr[pre].sum+1; if(l>=r) return u; if(k<=mid) tr[u].l=insert(tr[pre].l,l,mid,k); else tr[u].r=insert(tr[pre].r,mid+1,r,k); return u; } int query(int s,int t,int l,int r,int k) { if(l>=r) return l; int mid=(l+r)/2; int num=tr[tr[t].l].sum-tr[tr[s].l].sum; if(num>=k) return query(tr[s].l,tr[t].l,l,mid,k); else return query(tr[s].r,tr[t].r,mid+1,r,k-num); } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); m=unique(b+1,b+n+1)-(b+1); root[0]=build(1,m); for(int i=1;i<=n;i++) { int k=lower_bound(b+1,b+m+1,a[i])-b; root[i]=insert(root[i-1],1,m,k); } while(q--) { int x,y,z; scanf("%d%d%d",&x,&y,&z); int k=query(root[x-1],root[y],1,m,z); printf("%d\n",b[k]); } return 0; } ```