[模板] 可持久化数组

题目背景

UPDATE : 最后一个点时间空间已经放大

标题即题意

有了可持久化数组，便可以实现很多衍生的可持久化功能（例如：可持久化并查集）

题目描述

如题，你需要维护这样的一个长度为 N的数组，支持如下几种操作

1. 在某个历史版本上修改某一个位置上的值

2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

输入输出格式

输入格式：

输入的第一行包含两个正整数 N,M， 分别表示数组的长度和操作的个数。

第二行包含 N个整数，依次为初始状态下数组各位的值

接下来 M行每行包含3或4个整数，代表两种操作之一（ i 为基于的历史版本号）：

1. 对于操作1，格式为 \(v_i\) 1 \(loc_i\) \(val_i\),即为在版本\(v_i\)的基础上,
   将 \(a_{loc_i}\)​​ 修改为​

2. 对于操作2，格式为\(v_i\) 2 \(loc_i\)，即访问\(v_i\)版本\(loc_i\)的值。

输出格式：

输出包含若干行，依次为每个操作2的结果。

说明

\(1≤n≤10^6,1≤m≤10^6,1≤loc_i≤n,0≤v_i≤i,-10^9≤a_i,val_i≤10^9\)

Solution

主席树模板，直接上代码。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[1001000],b[1000100],root[1100000];
int tot=0;
struct NODE
{
    int ln,rn,val;
}t[20100000];
void build(int &node,int l,int r)
{
    
    node=++tot;
    if(l==r) {t[node].val=a[l];return;}
    int mid=(l+r)/2;
    build(t[node].ln,l,mid);
    build(t[node].rn,mid+1,r);
}
void gai(int &node,int last,int l,int r,int kk,int val)
{
    node=++tot;t[node]=t[last];
    if(l==r) {t[node].val=val;return;}
    int mid=(l+r)/2;
    if(kk<=mid) gai(t[node].ln,t[last].ln,l,mid,kk,val);
    else gai(t[node].rn,t[last].rn,mid+1,r,kk,val);
}
int cha(int node,int l,int r,int kk)
{
//  printf("%d %d %d %d\n",node,l,r,kk);
    if(l==r) return t[node].val;
    int mid=(l+r)/2;
    if(kk<=mid) return cha(t[node].ln,l,mid,kk);
    else return cha(t[node].rn,mid+1,r,kk);
}
int main()
{
    int n,m,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    build(root[0],1,n);
    for(int i=1;i<=m;i++)
    {
        int a1,a2,a3,a4;
        scanf("%d%d%d",&a1,&a2,&a3);
        if(a2==1)
        {
            scanf("%d",&a4);
            gai(root[i],root[a1],1,n,a3,a4);
        }
        else
        {
            printf("%d\n",cha(root[a1],1,n,a3));
            root[i]=root[a1];
        }
    }
}