题目链接

(模板)可持久化数组(可持久化线段树/平衡树)

题目背景

UPDATE : 最后一个点时间空间已经放大
标题即题意
有了可持久化数组,便可以实现很多衍生的可持久化功能(例如:可持久化并查集)

题目描述

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

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

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

输入格式

输入的第一行包含两个正整数$N,M$,分别表示数组的长度和操作的个数。
第二行包含$N$个整数,依次为初始状态下数组各位的值(依次为$a_i$,$1 \leq i \leq N$)。
接下来$M$行每行包含$3$或$4$个整数,代表两种操作之一($i$为基于的历史版本号):

  1. 对于操作$1$,格式为$v_i \ 1 \ {loc}_i \ {value}_i$,即为在版本$v_i$的基础上,将$a_{{loc}_i}$修改为${value}_i$
  2. 对于操作$2$,格式为$v_i \ 2 \ {loc}_i$,即访问版本$v_i$中的$a_{{loc}_i}$的值,生成一样版本的对象应为$v_i$

输出格式

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

样例输入

5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

样例输出

59
87
41
87
88
46

说明/提示

数据规模:
对于$30\%$的数据:$1 \leq N, M \leq {10}^3$
对于$50\%$的数据:$1 \leq N, M \leq {10}^4$
对于$70\%$的数据:$1 \leq N, M \leq {10}^5$
对于$100\%$的数据:$1 \leq N, M \leq {10}^6, 1 \leq {loc}_i \leq N, 0 \leq v_i < i, -{10}^9 \leq a_i, {value}_i \leq {10}^9$
经测试,正常常数的可持久化数组可以通过,请各位放心
数据略微凶残,请注意常数不要过大
另,此题I/O量较大,如果实在TLE请注意I/O优化
询问生成的版本是指你访问的那个版本的复制
样例说明:
一共$11$个版本,编号从$0-10$,依次为:

  • $0$ : 59 46 14 87 41
  • $1$ : 59 46 14 87 41
  • $2$ : 14 46 14 87 41
  • $3$ : 57 46 14 87 41
  • $4$ : 88 46 14 87 41
  • $5$ : 88 46 14 87 41
  • $6$ : 59 46 14 87 41
  • $7$ : 59 46 14 87 41
  • $8$ : 88 46 14 87 41
  • $9$ : 14 46 14 87 41
  • $10$ : 59 46 14 87 91

题解

很明显的一道数据结构板题,但是我只能从版本的要求看出是主席树,而且感觉我的建树方法会有浪费,还不知道怎么用平衡树做这道题,总的来说,我好菜啊。
因为每次修改操作是基于先前几次操作的版本进行操作的,所以我们可以把初始序列的信息存入第一棵线段树,然后每次修改(询问)的时候新建一棵树就好了。
其实对于每棵线段树,我们只要在它的叶子节点存入它的值就好了,而非叶子节点只需要存区间和左右儿子就好了。(这样的话会在非叶子节点上浪费很多空间,但是我也不知道有没有更好的办法)
接下来就是主席树的基本操作了,修改点值的时候,新建这个点以及它的所有祖先就好了。
如果不会主席树的话,可以到这里,看主席树的详解。
上代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int v,lo,val,x;
int a[1000009];
int ubb;
int kk;
int rt[1000009];
struct aa{
    int l,r;
    int s;
    int cd[2];
}p[30000009];
int len;
void init(int u,int l,int r){
    p[u].l=l;p[u].r=r;
    if(l==r){
        p[u].s=a[l];
        return;
    }
    int mid=(l+r)/2;
    if(l<=mid) init(p[u].cd[0]=++len,l,mid);
    if(mid+1<=r) init(p[u].cd[1]=++len,mid+1,r);
}
int lrt;
void dfs(int u,int x,int s){
    int mid=(p[u].l+p[u].r)/2;
    if(p[u].l==p[u].r){
        p[u].s=val;
        return;
    }
    len++;
    if(x<=mid){
        p[len]=p[p[u].cd[0]];
        p[u].cd[0]=len;
    }else{
        p[len]=p[p[u].cd[1]];
        p[u].cd[1]=len;
    }
    dfs(len,x,s);
}
void ask(int u,int x){
    int mid=(p[u].l+p[u].r)/2;
    if(p[u].l==p[u].r){
        printf("%d\n",p[u].s);
        return;
    }
    if(x<=mid) ask(p[u].cd[0],x);
    else ask(p[u].cd[1],x);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int j=1;j<=n;j++)
        scanf("%d",&a[j]);
    init(rt[0]=len=1,1,n);
    for(int j=1;j<=m;j++){
        scanf("%d%d%d",&v,&x,&lo);
        if(x==1){
            scanf("%d",&val);
            rt[++lrt]=++len;
            p[len]=p[rt[v]];
            dfs(len,lo,val);
        }else{
            rt[++lrt]=rt[v];
            ask(rt[v],lo);
        }
    }
    return 0;
}