洛谷 P3919 可持久化线段树 题解

题面

 

这题好水的说~很明显就是主席树的大板子

然而我交了3遍才调完所有的BUG，开好足够的数组，卡掉大大的常数；

 

针对与每次操作，change()会创建新节点,而ask()虽然也会更新左右儿子的节点编号，但并不会创建除根节点以外的点；

处理好以上change()和ask()的细节就可以轻松地切掉这道题；

#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
int n,m;
int a[50000100];
int cnt;
int b[50000010];
int L[50000100];
int R[50000100];
int root[5000010];
int build(int l,int r)
{
    int rt=++cnt;
    if(l==r){
        a[rt]=b[l];
        return rt;
    }
    L[rt]=build(l,mid);
    R[rt]=build(mid+1,r);
    return rt;
}
int change(int vpre,int vnow,int l,int r,int x,int value)
{
    int rt=++cnt;
    if(l==r){
        if(l==x){
            a[rt]=value;
        }
        return rt;
    }
    L[rt]=L[vpre];
    R[rt]=R[vpre];
    if(mid>=x){
        L[rt]=change(L[vpre],rt,l,mid,x,value);
    }
    else{
        R[rt]=change(R[vpre],rt,mid+1,r,x,value);
    }
    return rt;
}
int ask(int vpre,int vnow,int l,int r,int x)
{
    L[vnow]=L[vpre];
    R[vnow]=R[vpre];
    if(l==r){
        if(l==x){ 
            cout<<a[vnow]<<endl;
        }
        return vnow;
    }
    if(x<=mid) L[vnow]=ask(L[vpre],L[vnow],l,mid,x);
    else R[vnow]=ask(R[vpre],R[vnow],mid+1,r,x);
    return vnow;
}
int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    root[0]=build(1,n);
    for(int i=1;i<=m;i++){
        int v,opt; 
        scanf("%d%d",&v,&opt);
        if(opt==1){
            int weizhi,value;
            scanf("%d%d",&weizhi,&value);
            root[i]=change(root[v],cnt+1,1,n,weizhi,value);
        }
        else{
            int weizhi;
            scanf("%d",&weizhi);
            root[i]=++cnt;
            ask(root[v],cnt,1,n,weizhi);        
        }
    }
}