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

瑞源鸣 · 2019-03-01 22:16:04 · 题解

今天刚学完主席树，个人觉得还是比较简单的

• 先来波热身题

  依次给定n个数，再给定m个询问，问前i个数中第k大的数是多少，保证每次询问的位置递增。
  
  输入：
  5 3
  1 2 3 4 5
  2 2
  4 2
  5 3
  
  输出：
  1
  3
  3

• 我们来分析一波：

  如果学过平衡树，我们容易想到用平衡树解决，但事实上不需要。只需要用一个 基础 的数据结构—— 线段树 ！？ 如果没学过也无所谓，这有个大佬的平衡树的参考 博客 ，不懂的也可以问我，就顺便学了吧

  我们可以用 权值线段树 解决这个问题：

  1. 先建一颗有n个节点的空树
  2. 将 编号 作为 权值 存放进线段树，每个节点表示当前节点有多少棵 子树

  3. 查询的时候可以直接采取 线段树 的查询方式

     此时我们可以比较当前的 k 与根节点的 左儿子的size 比较，若小于左儿子，则往左儿子找，否则往右儿子找。找到叶子节点后输出对应的值即可。

     代码略（这不是关键）

• 回归这道题，是否觉得有一丢丢思路了

  1. 我们先建立n棵权值线段树
  2. 然后只需将第R棵线段树减去第(L-1)棵线段树，再跑一次热身题的那种方法即可

     • 若查询区间 [2,4]找第2小的数：

  3. 然后由于2>左儿子的1，所以往右儿子找，此时k更新为2-1=1。
  4. 再找下一层，由于1=1,所以往左儿子。找到根节点，返回对应的值。

• 问题来了！！！

  此时时间复杂度和空间复杂度都是O(n^2)! ! ! !

  接下来就引出我们重要的主席树的 核心 了:

  我们会发现，相邻的两棵树只有一条"链"不相同

  所以我们没有必要再开一颗完整的线段树，只需要在上一棵树的基础上重新增加一条链就可以了，剩下的不变的地方就沿用以前的就可以了。简单的思维！

  注意一下，由于数的范围比较大，所以我们需要离散化。因为要知道原来的值，所以开双向映射。同时需要一个root数组记录不同的树的根节点。

• code

  (码风丑，勿喷)

#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;
}