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

本篇题解发布者也是刚学的主席树,水平又low,还是第一次发题解 加上是先在代码上写了注释才写的题解,所以整个文章可能会有点重复啰嗦,有基础的可以直接看代码 在看的过程中有什么操作不懂可以结合代码看 如果有什么不对的地方还请大家多多包涵…… 前置要求: **线段树** 离散化 前缀和 可能比较好的观看体验: https://www.luogu.org/blog/0-1s/solution-p3834 (至少我看着还行) ----------------------------------------------- ## 思路 看到题目 我们首先考虑个0分写法 对每个[l,r]sort一遍求出答案 然后觉得不行 考虑数据结构 有一段数组 还有区间询问 那就看看线段树 题目是求第k小 所以**线段树维护的是[l,r]内数的出现次数** 看数据范围 2*10^5个数 数的范围是±10^9 因此用离散化 开个x[200010]就是线段树维护的数组 x[i]存第i小的数 再开个线段树的数组存区间内数的出现次数 大概是这样子 ……完了 我好像不会线段树了...... 再看题目 发现这样子做的话每个询问需要用[l,r]区间内的数的个数来建立一棵线段树 最多就有2*10^5棵线段树 时间空间都爆了 好了 GG ------------------------------------------------ 我们换个思路看 具体是什么思路我也不懂 先从简单入手 先求[1,r]的第k小 对于[1,i]树与[1,i+1]树 **后者只是多了a[i+1]的插入所带来的影响** 如图： [](https://imgchr.com/i/PBnMRg) 我们随便编一个数据 预处理如图(图丑 轻喷) [](https://imgchr.com/i/PBnui8) **对于每一个新的线段树 我们可以在旧的线段树的基础上通过 增加新的节点 来构建这颗树** 节省了大量的空间 我们可以用一个T[i]记录(1~i)线段树的根节点(容易看出根节点是一定是不同的) 这样算完了之后 我们就可以**通过T[i]来询问(1~i)线段树** 新的问题出现了 那如何解决区间问题呢 我们能求[1,i]的第k小(线段树的基本应用) 但是如何求[l,r]的第k小呢 想一下 [1,l]线段树是由插入 a[1]到a[l]的影响 构成的 [1,r]线段树是由插入 a[1]到a[r]的影响 构成的 是不是有点前缀和的感觉 那么 [l,r]线段树是由插入 a[l]到a[r]的影响 构成的 就等于 a[1]到a[r]的影响减去a[1]到a[l-1]的影响 所以 [l,r]线段树 = [1,r]线段树 - [1,l-1]线段树 是不是感觉很有道理 那具体怎么减呢 在线段树上 每个节点的值是这个节点所代表的区间内数字出现的次数 那么只要**在(r)线段树的每一个节点上减去(l-1)线段树上的相同位置的节点的值** 就行了 [](https://imgchr.com/i/PBnQzQ) 样例有点简单 但就是这个样子 ------------ ## 模拟代码解题过程 下面在给出题面样例的模拟过程 [](https://imgchr.com/i/PBnmIf) 预处理 [](https://imgchr.com/i/PBnKJS) 更新插入的数带来的新线段树 [](https://imgchr.com/i/PBn1Mj) 根据上面的方法来得到询问需要的线段树 然后就询问就完事了 下面给出代码 注释可能有点啰嗦 凑合着看吧……(代码旁边的字符是无聊瞎写的 无视即可) ------------ ```cpp #include <bits/stdc++.h> #define MAX 200010 using namespace std; int nodeNum; //所有节点的数量 //.............8888......... // int L[MAX<<5],R[MAX<<5],sum[MAX<<5]; //..............;888........ // //L[i]表示编号为i的节点的左儿子的编号 //...........888..888....... // //sum[i]表示编号为i的节点所代表的区间内数字出现的次数 //........888888..;....88... // int a[MAX],Hash[MAX]; //.......888.888.......888.. // //a[i]为原数组 Hash[i]为排序后数组 //.......888.888.......!888 // int T[MAX]; //.......88$.888........888. // //T[i]为插入i个点后的树的根节点编号 //......888..888.....888.... // //...........888.....888.... // int read() //...........8888888888o.... // { //............&8888888...... // int ans=0,flag=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') flag=-1;ch=getchar();} while(ch>='0'&&ch<='9') {ans=(ans<<3)+(ans<<1)+ch-'0';ch=getchar();} return ans*flag; } int build(int l,int r) //建一个空树(所有sum[i]都为0) { int num=++nodeNum; //num为当前节点编号 if(l!=r) { int m=(l+r)>>1; L[num]=build(l,m); R[num]=build(m+1,r); } return num; //返回当前节点的编号 } int update(int pre,int l,int r,int x) //pre为旧树该位置节点的编号 { int num=++nodeNum; //新建节点的编号 L[num]=L[pre];R[num]=R[pre];sum[num]=sum[pre]+1; //该节点左右儿子初始化为旧树该位置节点的左右儿子 //因为插入的a[i](或Hash[x])在该节点所代表的区间中 所以sum++ if(l!=r) { int m=(l+r)>>1; if(x<=m) L[num]=update(L[pre],l,m,x); //x出现在左子树 因此右子树保持与旧树相同 修改左子树 else R[num]=update(R[pre],m+1,r,x); } return num; } int query(int u,int v,int l,int r,int k) //第k小 { if(l==r) return Hash[l]; //找到第k小 l是节点编号 所以答案是Hash[l] int m=(l+r)>>1; int num=sum[L[v]]-sum[L[u]]; //用第一次模拟 这样比较容易看得懂 此时u=l-1 v=r //则num= (1~r)树的左节点数字出现的次数 - (1~(l-1))树的左节点数字出现的次数 //即num等于([l,r])树左儿子数字出现的次数 if(num>=k) return query(L[u],L[v],l,m,k); //当 左儿子数字出现的次数大于等于k 时 意味着 第k小的数字在左子树处 else return query(R[u],R[v],m+1,r,k-num); //否则去右子树处找第k-num小的数字 } int main() { int n=read(),m=read(); for(int i=1;i<=n;i++) {a[i]=read();Hash[i]=a[i];} sort(Hash+1,Hash+1+n); int size=unique(Hash+1,Hash+1+n)-Hash-1; //size为线段树维护的数组的大小==Hash数组中不重复的数字的个数 T[0]=build(1,size); //初始化 建立一颗空树 并把该树的根节点的编号赋值给T[0] for(int i=1;i<=n;i++) { int x=lower_bound(Hash+1,Hash+1+size,a[i])-Hash; //在Hash的 [1,size+1)--->[1,size] 中二分查找第一个 // 大于等于(在这里可以看成等于) a[i]的Hash[x] T[i]=update(T[i-1],1,size,x); //更新a[i]带来的影响 //并将新树的根节点的编号赋值给T[i] } while(m--) { int l=read(),r=read(),k=read(); printf("%d\n",query(T[l-1],T[r],1,size,k)); //因为a[l]有影响 所以是T[l-1] } return 0; } ```