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

    • 1.4K通过
    • 3.6K提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 可持久化 平衡树 线段树 递归 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    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} $的值

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。