Stone Age Problem

题意翻译

### 题目描述 数组 $a$ 有 $n$ 个元素，需要进行 $q$ 次操作。 操作1：将第 $i$ 号元素改为 $x$ 操作2：将数组中所有元素改为 $x$ 每次操作完成后，输出当前数组中所有元素的总和。 ### 输入格式 第一行两个整数 $n,q(1\le n,q \le2\times 10^5)$ 第二行 $n$ 个整数，表示 $a$ 中的元素 $(1\le a_i\le10^9)$ 接下来有 $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$ 行，每行一个整数，表示当前数组 $a$ 中所有元素的和

题目描述

Once upon a time Mike and Mike decided to come up with an outstanding problem for some stage of ROI (rare olympiad in informatics). One of them came up with a problem prototype but another stole the idea and proposed that problem for another stage of the same olympiad. Since then the first Mike has been waiting for an opportunity to propose the original idea for some other contest... Mike waited until this moment! You are given an array $ a $ of $ n $ integers. You are also given $ q $ queries of two types: - Replace $ i $ -th element in the array with integer $ x $ . - Replace each element in the array with integer $ x $ . After performing each query you have to calculate the sum of all elements in the array.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 2 \cdot 10^5 $ ) — the number of elements in the array and the number of queries, respectively. The second line contains $ n $ integers $ a_1, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — elements of the array $ a $ . Each of the following $ q $ lines contains a description of the corresponding query. Description begins with integer $ t $ ( $ t \in \{1, 2\} $ ) which denotes a type of the query: - If $ t = 1 $ , then two integers $ i $ and $ x $ are following ( $ 1 \le i \le n $ , $ 1 \le x \le 10^9 $ ) — position of replaced element and it's new value. - If $ t = 2 $ , then integer $ x $ is following ( $ 1 \le x \le 10^9 $ ) — new value of each element in the array.

输出格式

Print $ q $ integers, each on a separate line. In the $ i $ -th line print the sum of all elements in the array after performing the first $ i $ queries.

输入输出样例

输入样例 #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

说明

Consider array from the example and the result of performing each query: 1. Initial array is $ [1, 2, 3, 4, 5] $ . 2. After performing the first query, array equals to $ [5, 2, 3, 4, 5] $ . The sum of all elements is $ 19 $ . 3. After performing the second query, array equals to $ [10, 10, 10, 10, 10] $ . The sum of all elements is $ 50 $ . 4. After performing the third query, array equals to $ [10, 10, 10, 10, 11 $ \]. The sum of all elements is $ 51 $ . 5. After performing the fourth query, array equals to $ [10, 10, 10, 1, 11] $ . The sum of all elements is $ 42 $ . 6. After performing the fifth query, array equals to $ [1, 1, 1, 1, 1] $ . The sum of all elements is $ 5 $ .

**题目大意：**
给定一个含有n个整数的数组a，需要执行q次操作。有两种操作类型：

操作1：将数组中第i个元素替换为x。
操作2：将数组中所有元素替换为x。

在每次操作之后，计算并输出数组a中所有元素的总和。

**输入数据格式：**
第一行包含两个整数n和q（1≤n,q≤2×10^5），分别表示数组元素的数量和操作的次数。
第二行包含n个整数a_1, ..., a_n（1≤a_i≤10^9），表示数组a的元素。
接下来q行，每行描述一个操作，首先是一个整数t（t∈{1,2}）表示操作的类型：
- 如果t=1，接着输入两个整数i和x（1≤i≤n, 1≤x≤10^9），表示要替换的元素的位置和新值。
- 如果t=2，接着输入一个整数x（1≤x≤10^9），表示数组中每个元素的新值。

**输出数据格式：**
输出共q行，每行一个整数，表示执行完前i个操作后数组a中所有元素的总和。

**输入输出样例：**
**输入样例 #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。**题目大意：** 给定一个含有n个整数的数组a，需要执行q次操作。有两种操作类型： 操作1：将数组中第i个元素替换为x。 操作2：将数组中所有元素替换为x。 在每次操作之后，计算并输出数组a中所有元素的总和。 **输入数据格式：** 第一行包含两个整数n和q（1≤n,q≤2×10^5），分别表示数组元素的数量和操作的次数。 第二行包含n个整数a_1, ..., a_n（1≤a_i≤10^9），表示数组a的元素。 接下来q行，每行描述一个操作，首先是一个整数t（t∈{1,2}）表示操作的类型： - 如果t=1，接着输入两个整数i和x（1≤i≤n, 1≤x≤10^9），表示要替换的元素的位置和新值。 - 如果t=2，接着输入一个整数x（1≤x≤10^9），表示数组中每个元素的新值。 **输出数据格式：** 输出共q行，每行一个整数，表示执行完前i个操作后数组a中所有元素的总和。 **输入输出样例：** **输入样例 #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。