Monoblock

题意翻译

我们定义连续 $k$（$k$ 尽可能大）个相同的数被称为一个“块”。一个序列的“块”数就相当于将其直接去重后的序列长度。 给定一个长度 $n$ 的序列和 $m$ 次询问。对于每次询问，有两个数 $i,x$，先将 $a_i$ 改为 $x$，然后输出 $\sum\limits_{l=1}^n\sum\limits_{r=l}^ng(l,r)$，其中 $g(l,r)$ 表示 $a_{l\sim r}$ 的“块”数。 Translated by @_JYqwq_

题目描述

Stanley has decided to buy a new desktop PC made by the company "Monoblock", and to solve captcha on their website, he needs to solve the following task. The awesomeness of an array is the minimum number of blocks of consecutive identical numbers in which the array could be split. For example, the awesomeness of an array - $ [1, 1, 1] $ is $ 1 $ ; - $ [5, 7] $ is $ 2 $ , as it could be split into blocks $ [5] $ and $ [7] $ ; - $ [1, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9] $ is 3, as it could be split into blocks $ [1] $ , $ [7, 7, 7, 7, 7, 7, 7] $ , and $ [9, 9, 9, 9, 9, 9, 9, 9, 9] $ . You are given an array $ a $ of length $ n $ . There are $ m $ queries of two integers $ i $ , $ x $ . A query $ i $ , $ x $ means that from now on the $ i $ -th element of the array $ a $ is equal to $ x $ . After each query print the sum of awesomeness values among all subsegments of array $ a $ . In other words, after each query you need to calculate $ $\sum\limits_{l = 1}^n \sum\limits_{r = l}^n g(l, r), $ $ where $ g(l, r) $ is the awesomeness of the array $ b = \[a\_l, a\_{l + 1}, \\ldots, a\_r\]$.

输入输出格式

输入格式

In the first line you are given with two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the array $ a $ . In the next $ m $ lines you are given the descriptions of queries. Each line contains two integers $ i $ and $ x $ ( $ 1 \leq i \leq n $ , $ 1 \leq x \leq 10^9 $ ).

输出格式

Print the answer to each query on a new line.

输入输出样例

输入样例 #1

5 5
1 2 3 4 5
3 2
4 2
3 1
2 1
2 2

输出样例 #1

29
23
35
25
35

说明

After the first query $ a $ is equal to $ [1, 2, 2, 4, 5] $ , and the answer is $ 29 $ because we can split each of the subsegments the following way: 1. $ [1; 1] $ : $ [1] $ , 1 block; 2. $ [1; 2] $ : $ [1] + [2] $ , 2 blocks; 3. $ [1; 3] $ : $ [1] + [2, 2] $ , 2 blocks; 4. $ [1; 4] $ : $ [1] + [2, 2] + [4] $ , 3 blocks; 5. $ [1; 5] $ : $ [1] + [2, 2] + [4] + [5] $ , 4 blocks; 6. $ [2; 2] $ : $ [2] $ , 1 block; 7. $ [2; 3] $ : $ [2, 2] $ , 1 block; 8. $ [2; 4] $ : $ [2, 2] + [4] $ , 2 blocks; 9. $ [2; 5] $ : $ [2, 2] + [4] + [5] $ , 3 blocks; 10. $ [3; 3] $ : $ [2] $ , 1 block; 11. $ [3; 4] $ : $ [2] + [4] $ , 2 blocks; 12. $ [3; 5] $ : $ [2] + [4] + [5] $ , 3 blocks; 13. $ [4; 4] $ : $ [4] $ , 1 block; 14. $ [4; 5] $ : $ [4] + [5] $ , 2 blocks; 15. $ [5; 5] $ : $ [5] $ , 1 block; which is $ 1 + 2 + 2 + 3 + 4 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 29 $ in total.

**题目大意：**

题目定义了一个数组的“块”数，指的是将数组中连续相同的数进行合并后得到的块的数量。例如，数组 `[1, 1, 1]` 的块数为 `1`，因为它可以合并为一个块 `[1, 1, 1]`。

给定一个长度为 `n` 的数组 `a` 和 `m` 次询问。每次询问包括两个整数 `i` 和 `x`，表示将数组 `a` 中第 `i` 个位置的数改为 `x`。修改后，需要计算所有子数组的“块”数之和。具体来说，对于每次询问，需要计算 $\sum\limits_{l=1}^n\sum\limits_{r=l}^ng(l,r)$，其中 `g(l,r)` 表示数组 `a` 中从第 `l` 个到第 `r` 个元素的子数组的“块”数。

**输入输出数据格式：**

**输入格式：**
- 第一行包含两个整数 `n` 和 `m`（$1 \leq n, m \leq 10^5$），分别表示数组 `a` 的长度和询问次数。
- 第二行包含 `n` 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 `a` 的初始值。
- 接下来的 `m` 行，每行包含两个整数 `i` 和 `x`（$1 \leq i \leq n$，$1 \leq x \leq 10^9$），表示一次询问，即将数组 `a` 中第 `i` 个位置的数改为 `x`。

**输出格式：**
- 对于每次询问，输出一行，表示修改后所有子数组的“块”数之和。

**输入输出样例：**

**输入样例 #1：**
```
5 5
1 2 3 4 5
3 2
4 2
3 1
2 1
2 2
```

**输出样例 #1：**
```
29
23
35
25
35
```

**说明：**

第一个询问后，数组 `a` 变为 `[1, 2, 2, 4, 5]`，其所有子数组的“块”数之和为 `29`。**题目大意：** 题目定义了一个数组的“块”数，指的是将数组中连续相同的数进行合并后得到的块的数量。例如，数组 `[1, 1, 1]` 的块数为 `1`，因为它可以合并为一个块 `[1, 1, 1]`。 给定一个长度为 `n` 的数组 `a` 和 `m` 次询问。每次询问包括两个整数 `i` 和 `x`，表示将数组 `a` 中第 `i` 个位置的数改为 `x`。修改后，需要计算所有子数组的“块”数之和。具体来说，对于每次询问，需要计算 $\sum\limits_{l=1}^n\sum\limits_{r=l}^ng(l,r)$，其中 `g(l,r)` 表示数组 `a` 中从第 `l` 个到第 `r` 个元素的子数组的“块”数。 **输入输出数据格式：** **输入格式：** - 第一行包含两个整数 `n` 和 `m`（$1 \leq n, m \leq 10^5$），分别表示数组 `a` 的长度和询问次数。 - 第二行包含 `n` 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 `a` 的初始值。 - 接下来的 `m` 行，每行包含两个整数 `i` 和 `x`（$1 \leq i \leq n$，$1 \leq x \leq 10^9$），表示一次询问，即将数组 `a` 中第 `i` 个位置的数改为 `x`。 **输出格式：** - 对于每次询问，输出一行，表示修改后所有子数组的“块”数之和。 **输入输出样例：** **输入样例 #1：** ``` 5 5 1 2 3 4 5 3 2 4 2 3 1 2 1 2 2 ``` **输出样例 #1：** ``` 29 23 35 25 35 ``` **说明：** 第一个询问后，数组 `a` 变为 `[1, 2, 2, 4, 5]`，其所有子数组的“块”数之和为 `29`。