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.

题意翻译

我们定义连续 $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_