← 返回题目列表

Codeforces · 1679/B

B. 石器时代问题

中文机器翻译题面 查看原题

很久以前,Mike 和 Mike 决定为 ROI 的某个阶段提出一个突出问题(罕见的信息学奥林匹克竞赛)。其中一个人提出了一个问题原型,但另一个人窃取了这个想法,并在同一届奥林匹克竞赛的另一个阶段提出了这个问题。从那时起,第一个迈克就一直在等待机会,为其他比赛提出最初的想法……迈克等到了这一刻!

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您还会收到两种类型的 $$$q$$$ 查询:

- 将数组中的第 $$$i$$$ 元素替换为整数 $$$x$$$。
- 将数组中的每个元素替换为整数 $$$x$$$。

执行每个查询后,您必须计算数组中所有元素的总和。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) - 分别是数组中的元素数量和查询数量。

第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

以下 $$$q$$$ 行中的每一行都包含相应查询的描述。描述以整数 $$$t$$$ ($$$t \in \{1, 2\}$$$) 开头,表示查询的类型:

- 如果 $$$t = 1$$$,则后面有两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 10^9$$$) — 被替换元素的位置及其新值。
- 如果 $$$t = 2$$$,则后面是整数 $$$x$$$ ($$$1 \le x \le 10^9$$$) — 数组中每个元素的新值。

输出

打印 $$$q$$$ 整数,每个整数占一行。在执行第一个 $$$i$$$ 查询后,在第 $$$i$$$ 行中打印数组中所有元素的总和。

示例

输入 #1

5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1

输出 #1

19
50
51
42
5

注意

考虑示例中的数组以及执行每个查询的结果:

1. 初始数组为 $$$[1, 2, 3, 4, 5]$$$。
2. 执行第一次查询后,数组等于$$$[5, 2, 3, 4, 5]$$$。所有元素的总和为 $$$19$$$。
3. 执行第二次查询后,数组等于$$$[10, 10, 10, 10, 10]$$$。所有元素的总和为 $$$50$$$。
4. 执行第三次查询后,数组等于$$$[10, 10, 10, 10, 11$$$]。所有元素的总和为 $$$51$$$。
5. 执行第四次查询后,数组等于$$$[10, 10, 10, 1, 11]$$$。所有元素的总和为 $$$42$$$。
6. 执行第五次查询后,数组等于$$$[1, 1, 1, 1, 1]$$$。所有元素的总和为$$$5$$$。