链接: https://cses.fi/problemset/task/1737

板块: Range Queries

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务是对一组数组进行维护，这组数组初始时只有一个数组。你需要处理以下类型的查询：

1. 将数组 $k$ 中位置 $a$ 的值设为 $x$。
2. 计算数组 $k$ 中区间 $[a,b]$ 的数值之和。
3. 创建数组 $k$ 的一个副本，并将其添加到数组列表的末尾。

输入

第一行输入包含两个整数 $n$ 和 $q$：分别表示数组大小和查询数量。

下一行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$：数组的初始内容。

最后有 $q$ 行描述查询。每行格式为以下之一："$1$ $k$ $a$ $x$"、"$2$ $k$ $a$ $b$" 或 "$3$ $k$"。

输出

对每个求和查询输出其答案。

数据范围

$1 \le n, q \le 2 \cdot 10^5$ $1 \le t_i, x \le 10^9$ $1 \le a \le b \le n$

样例输入

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

样例输出

13
13
13
15