5464. 范围查询与复制（Range Queries and Copies）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 你的任务是维护一个数组列表，初始时列表中只有一个数组。你需要高效地处理以下三种类型的查询： 1. 将第 $k$ 个数组中位置 $a$ 的值修改为 $x$。 2. 计算第 $k$ 个数组在区间 $[a,b]$ 内的元素之和。 3. 创建第 $k$ 个数组的一个副本，并将其添加到列表的末尾。 ## 输入格式 第一行包含两个整数 $n$ 和 $q$，分别表示数组大小和查询数量。 第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$，表示初始数组的元素。 接下来 $q$ 行描述查询，格式为以下之一： - `1 k a x`：将第 $k$ 个数组中位置 $a$ 的值修改为 $x$。 - `2 k a b`：计算第 $k$ 个数组在区间 $[a,b]$ 内的元素之和。 - `3 k`：复制第 $k$ 个数组并将副本添加至末尾。 ## 输出格式 对于每个求和查询，输出计算出的结果。 ## 输入输出样例 ### 输入 #1 ``` 5 6 2 3 1 2 5 3 1 2 1 1 5 2 2 1 5 1 2 2 5 2 1 1 5 2 2 1 5 ``` ### 输出 #1 ``` 13 15 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n, q \le 2 \cdot 10^5$ - $1 \le t_i, x \le 10^9$ - $1 \le a \le b \le n$