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

今天刚学完主席树，~~个人觉得还是比较简单的~~ ------------ - ### **先来波热身题** ``` 依次给定n个数，再给定m个询问，问前i个数中第k大的数是多少，保证每次询问的位置递增。 输入： 5 3 1 2 3 4 5 2 2 4 2 5 3 输出： 1 3 3 ``` ------------ - ### 我们来分析一波： 如果学过平衡树，我们容易想到用平衡树解决，但事实上不需要。只需要用一个 ~~基础~~ 的数据结构—— **线段树** ！？ 如果没学过也无所谓，这有个大佬的平衡树的参考 **[博客](https://www.luogu.org/blog/teljian/solution-p3369)** ，不懂的也可以问我，~~就顺便学了吧~~ 我们可以用 **权值线段树** 解决这个问题： 1. 先建一颗有n个节点的空树 1. 将 **编号** 作为 **权值** 存放进线段树，每个节点表示当前节点有多少棵 **子树** 1. 查询的时候可以直接采取 **线段树** 的查询方式  此时我们可以比较当前的 **k** 与根节点的 **左儿子的size** 比较，若小于左儿子，则往左儿子找，否则往右儿子找。找到叶子节点后输出对应的值即可。 ##### ~~代码略（这不是关键）~~ ------------ - ## **回归这道题，是否觉得有一丢丢思路了** 1. 我们先建立n棵权值线段树 1. 然后只需将第R棵线段树减去第(L-1)棵线段树，再跑一次热身题的那种方法即可 - ### 若查询区间 [2,4]找第2小的数：  1. 然后由于2>左儿子的1，所以往右儿子找，此时k更新为2-1=1。 1. 再找下一层，由于1=1,所以往左儿子。找到根节点，返回对应的值。 ------------ - ### 问题来了！！！ 此时时间复杂度和空间复杂度都是O(n^2)! ! ! ! 接下来就引出我们重要的主席树的 **核心** 了: ### 我们会发现，相邻的两棵树只有一条"链"不相同 所以我们没有必要再开一颗完整的线段树，只需要在上一棵树的基础上重新增加一条链就可以了，剩下的不变的地方就沿用以前的就可以了。~~简单的思维！~~ #### 注意一下，由于数的范围比较大，所以我们需要离散化。因为要知道原来的值，所以开双向映射。同时需要一个root数组记录不同的树的根节点。  ------------ - # code (码风丑，勿喷) ```cpp #include<cstdio> #include<algorithm> using namespace std; const int M=(2e5)+10; #define ls tree[now].l #define rs tree[now].r int n,m; int k,N; int root[M]; int a[M],ys[M]; //a存离散化后的数,ys建立离散化后与原数的映射关系,root为森林的不同根节点 struct Node{ int num; int id; }q[M]; struct node{ int l,r; int size; }tree[M<<5];//多开 1<<5 的空间 inline int read(){ int f=1,x=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool cmp(Node x,Node y){//求第k小的数,所以从小到大排序 return x.num<y.num; } void lsh(){//离散化模板 a[q[1].id]=++N; ys[N]=q[1].num;//注意存映射的点 for(int i=2;i<=n;i++){ if(q[i].num!=q[i-1].num) N++; a[q[i].id]=N; ys[N]=q[i].num; } } int build(int l,int r){//动态建树,防止数组越界或开不够 int now=++k;//加点 if(l<r){ int mid=(l+r)>>1; ls=build(l,mid);//更新左儿子 rs=build(mid+1,r);//更新右儿子 } return now; } int update(int pre,int l,int r,int x){//建权值线段树 int now=++k; tree[now].size=tree[pre].size+1;//此线段树的点数为上一棵的点数+1 ls=tree[pre].l; rs=tree[pre].r; //继承上一棵线段树 if(l<r){//寻找需要更新的链 int mid=(l+r)>>1; if(x>mid) rs=update(rs,mid+1,r,x);//在右儿子更新 else ls=update(ls,l,mid,x);//在左儿子更新 } return now; } int query(int u,int v,int l,int r,int x){//查询操作 if(l==r) return l;//找到第k小值 //第r棵线段树左儿子-第(l-1)棵线段树左儿子的值 int t=tree[tree[v].l].size-tree[tree[u].l].size; int mid=(l+r)>>1; if(x<=t) return query(tree[u].l,tree[v].l,l,mid,x);//在左儿子上 else return query(tree[u].r,tree[v].r,mid+1,r,x-t);//在右儿子上 } int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ q[i].num=read(); q[i].id=i; } sort(q+1,q+n+1,cmp); lsh(); root[0]=build(1,N);//建一颗空的线段树 for(int i=1;i<=n;i++)//建n棵线段树,边加点边建树 root[i]=update(root[i-1],1,N,a[i]); for(int i=1,l,r,x;i<=m;i++){ l=read();r=read();x=read(); printf("%d\n",ys[query(root[l-1],root[r],1,N,x)]); //[l,r]就等价于 第r棵线段树-第(l-1)棵线段树 的k小值,返回该节点映射的值 } return 0; } ```