题解 P3919 【【模板】可持久化数组（可持久化线段树/平衡树）】

我叫小明0_0 · 2017-08-17 23:09:00 · 题解

第一眼可持久化线段树...嘛，那就写吧

数组开太大交上去回全RE...长见识

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int maxn = 1000009;

int rt[maxn],a[maxn];
struct sg_tree{int val,lson,rson;}node[maxn*20];
int n,m,tot;

inline int read()
{
    int x=0,f=1;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;
}

void build(int &now,int l,int r)
{
    now=++tot;
    if(l==r){node[now].val=a[l];return ;}
    int mid=(l+r)>>1;
    build(node[now].lson,l,mid);
    build(node[now].rson,mid+1,r);
}
void insert(int &now,int last,int l,int r,int pos,int val)
{
    now=++tot;node[now]=node[last];
    if(l==r){node[now].val=val;return ;}
    int mid=(l+r)>>1;
    if(pos<=mid) insert(node[now].lson,node[last].lson,l,mid,pos,val);
    else insert(node[now].rson,node[last].rson,mid+1,r,pos,val);
}
int query(int now,int l,int r,int pos)
{
    if(l==r) return node[now].val;
    int mid=(l+r)>>1;
    if(pos<=mid) return query(node[now].lson,l,mid,pos);
    else return query(node[now].rson,mid+1,r,pos);
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(rt[0],1,n);
    for(int i=1;i<=m;i++)
    {
        int ver=read(),opt=read(),pos=read();
        if(opt==1) insert(rt[i],rt[ver],1,n,pos,read());
        else printf("%d\n",query(rt[ver],1,n,pos)),rt[i]=rt[ver];
    }
    return 0;
}
```cpp
时空复杂度都是O((n+q)logn)级的

但是不强制在线的可持久化都是耍流氓，我们考虑离线

发现每个版本都有唯一一个前驱，一定组成一棵树结构

对这棵树dfs，每到一个点如果是修改就直接修改，询问就直接得到答案

离开一个点时如果是修改就改回去

总复杂度O(n)

```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000009;

int first[maxn];
struct edg{int next,to;}e[maxn];
struct node{int ver,opt,pos,val;}q[maxn];
int n,m,e_sum;
int a[maxn],ans[maxn];
bool uuz[maxn];

inline int read()
{
    int x=0,f=1;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;
}
void add_edg(int x,int y)
{
    e_sum++;
    e[e_sum].next=first[x];
    first[x]=e_sum;
    e[e_sum].to=y;
}

void dfs(int x)
{
    int last;
    if(q[x].opt==1) last=a[q[x].pos],a[q[x].pos]=q[x].val;
    else ans[x]=a[q[x].pos];
    for(int i=first[x];i;i=e[i].next)
    {
        int w=e[i].to;
        dfs(w);
    }
    if(q[x].opt==1) a[q[x].pos]=last;
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++)
    {
        q[i].ver=read();q[i].opt=read();q[i].pos=read();
        if(q[i].opt==1) q[i].val=read();else uuz[i]=1;
        add_edg(q[i].ver,i);
    }
    dfs(0);
    for(int i=1;i<=m;i++) if(uuz[i]) printf("%d\n",ans[i]);
    return 0;
}
```cpp