最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 【模板】可持久化线段树 1(可持久化数组)

    正文概述 陈老师   2026-01-20 15:15:45  

    题目背景

    标题即题意

    有了可持久化数组,便可以实现很多衍生的可持久化功能(例如:可持久化并查集)

    题目描述

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

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

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

    此外,每进行一次操作,就会生成一个新的版本。版本编号即为当前操作的编号(从 11 开始编号,版本 00 表示初始状态数组)。

    对于操作 22,即为生成一个完全一样的版本,不作任何改动。即,询问生成的版本是询问所访问的那个版本的复制。

    输入格式

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

    第二行包含 N N 个整数,依次为初始状态下数组各位的值(依次为 ai a_i ,1≤i≤N 1 \leq i \leq N )。

    接下来 M M 行每行包含 33 或 44 个整数,代表两种操作之一(设当前是第 ii 次操作):

    1. 对于操作 11,格式为 v 1 p c,即为在版本 v v 的基础上,将 ap a_{p} 修改为 cc。

    2. 对于操作 22,格式为 v 2 p,即访问版本 v v 中的 ap a_{p} 的值,注意:生成一样版本的对象应为 vv。

    输出格式

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

    样例

    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
    

    提示

    样例解释

    所有操作结束后,总共生成了 1111 个版本,编号为 0∼100 \sim 10,依次为:

    版本 00:59 46 14 87 41,

    版本 11:59 46 14 87 41,

    版本 22:14 46 14 87 41,

    版本 33:57 46 14 87 41,

    版本 44:88 46 14 87 41,

    版本 55:88 46 14 87 41,

    版本 66:59 46 14 87 41,

    版本 77:59 46 14 87 41,

    版本 88:88 46 14 87 41,

    版本 99:14 46 14 87 41,

    版本 1010:59 46 14 87 91。

    数据范围

    对于 30%30\% 的数据,1≤N,M≤103 1 \leq N, M \leq {10}^3 。

    对于 50%50\% 的数据,1≤N,M≤104 1 \leq N, M \leq {10}^4 。

    对于 70%70\% 的数据,1≤N,M≤105 1 \leq N, M \leq {10}^5 。

    对于 100%100\% 的数据:

    • 1≤N,M≤106 1 \leq N, M \leq {10}^6;
    • 1≤p≤N1 \leq p \leq N;
    • 设当前是第 xx 次操作,0≤v<x0 \leq v < x;
    • −109≤ai,c≤109-{10}^9 \leq a_i,c \leq {10}^9。
    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 【模板】可持久化线段树 1(可持久化数组)