题解：P3919 【模板】可持久化线段树 1（可持久化数组）

· · 题解

这题一眼裸的可持久化线段树，但可持久化线段树是 O(n \log n) 的，我们有 O(n) 的离线 dfs 做法。

算法介绍

我们把所有版本抽象成一棵树，那么每个版本的子节点为由该版本为基础生成的所有版本，树上的边则为所有操作。我们从根节点开始 dfs，当走过一条边时，进行修改操作，更新数组的值。当走到一个版本 v 时，遍历这个节点的询问，每个询问 (v,p) 的答案即为 a_{p}。

正确性证明

假设目前走到了版本 v，那么你一定经过了这个版本的所有父节点。也就是说，你一定进行了从初始状态后的所有修改操作。那么，此时的 a 数组就是当前版本的数组，此时直接处理询问就行了。

代码实现

有个小细节，每一个版本可能有多个询问，此时应使用一个 vector 来存每个版本的询问。

还有个特殊情况，对于每个询问 (v,p)，需生成一个新版本 i，与版本 v 相同。那么我们就将 i 与 v 的父节点连边，修改操作与版本 v 相同，这样 dfs 到这个版本时就会与版本 v 保持一致。

代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,z;//i->x,a[y]=z
};
int n,m,a[2000010],ans[2000010],x[2000010],y[2000010],z[2000010],cnt;
vector<pair<int,int>>q[2000010];//{a[i]=x,id}
vector<node>v[2000010];
void dfs(int xx){
    for(int i=0;i<q[xx].size();i++)ans[q[xx][i].second]=a[q[xx][i].first];//处理答案
    for(int i=0;i<v[xx].size();i++){//遍历出边
        int x=v[xx][i].x,y=v[xx][i].y,z=v[xx][i].z,tmp=a[y];//tmp记录此时a[y]值，方便还原
        a[y]=z;//修改操作
        dfs(x);
        a[y]=tmp;//还原
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int t=1e6+1;//t为根节点，以及版本0的父节点，因为询问0时会产生一个与0相同的版本，就全部向t连边
    x[0]=t,y[0]=1,z[0]=a[1];
    v[x[0]].push_back({0,y[0],z[0]});//t->0
    for(int i=1;i<=m;i++){
        int op;
        cin>>x[i]>>op>>y[i];
        int xx=x[i],yy=y[i],zz;
        if(op==1){
            cin>>z[i];zz=z[i];
            v[xx].push_back({i,yy,zz});
        }
        else{
            v[x[xx]].push_back({i,y[xx],z[xx]}),q[i].push_back({yy,++cnt});//复制版本，加入询问
            x[i]=x[xx];
            y[i]=y[xx];
            z[i]=z[xx];//记得把x,y,z数组改掉，否则复制该版本时会出问题
        }
    }
    dfs(t);//从根节点t开始dfs
    for(int i=1;i<=cnt;i++)cout<<ans[i]<<"\n";
}