P3919 【模板】可持久化线段树 1（可持久化数组）

题目描述

维护这一个长度为 $N$ 的数组 $a_i$，有 $M$ 次操作，操作如下两种：

• v 1 p c，即为在版本 $v$ 的基础上，将 $a_{p}$ 修改为 $c$。

• v 2 p，即访问版本 $v$ 中的 $a_{p}$ 的值。

此外，每进行一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 $1$ 开始编号，版本 $0$ 表示初始状态数组）。

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

输入格式

第一行两个正整数 $N, M$。

第二行 $N$ 个整数$a_i$，$1 \leq i \leq N$）。

接下来 $M$ 行每行包含 $3$ 或 $4$ 个整数，代表两种操作之一。

输出格式

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

输入输出样例 #1

输入 #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 p \leq N$；
• 设当前是第 $x$ 次操作，$0 \leq v < x$；
• $-{10}^9 \leq a_i,c \leq {10}^9$。

样例说明

所有操作结束后，总共生成了 $11$ 个版本，编号为 $0 \sim 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。