欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[模板] 可持久化数组

程序员文章站 2024-03-04 12:04:05
...

题目背景

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