CF1715C Monoblock

Stanley 决定购买由“Monoblock”公司生产的新台式电脑。为了在他们的网站上通过验证码，他需要解决如下任务。 一个数组的“awesomeness”（精彩度）定义为：将该数组划分为若干个连续且相同数字的区块，所需的最小区块数。例如： - $[1, 1, 1]$ 的精彩度为 $1$； - $[5, 7]$ 的精彩度为 $2$，因为可以划分为 $[5]$ 和 $[7]$ 两个区块； - $[1, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9]$ 的精彩度为 $3$，因为可以划分为 $[1]$、$[7, 7, 7, 7, 7, 7, 7]$ 和 $[9, 9, 9, 9, 9, 9, 9, 9, 9]$ 三个区块。 给定一个长度为 $n$ 的数组 $a$。有 $m$ 个查询，每个查询包含两个整数 $i$ 和 $x$。一次查询 $i, x$ 表示从现在起，将数组 $a$ 的第 $i$ 个元素赋值为 $x$。 每次查询后，输出数组 $a$ 所有子区间的精彩度之和。换句话说，每次查询后，你需要计算 $$ \sum\limits_{l = 1}^n \sum\limits_{r = l}^n g(l, r) $$ 其中 $g(l, r)$ 表示区间 $b = [a_l, a_{l + 1}, \ldots, a_r]$ 的精彩度。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$）。 第二行包含 $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$ 变为 $[1, 2, 2, 4, 5]$，答案为 $29$，因为每个子区间的精彩度如下： 1. $[1; 1]$：$[1]$，1 个区块； 2. $[1; 2]$：$[1] + [2]$，2 个区块； 3. $[1; 3]$：$[1] + [2, 2]$，2 个区块； 4. $[1; 4]$：$[1] + [2, 2] + [4]$，3 个区块； 5. $[1; 5]$：$[1] + [2, 2] + [4] + [5]$，4 个区块； 6. $[2; 2]$：$[2]$，1 个区块； 7. $[2; 3]$：$[2, 2]$，1 个区块； 8. $[2; 4]$：$[2, 2] + [4]$，2 个区块； 9. $[2; 5]$：$[2, 2] + [4] + [5]$，3 个区块； 10. $[3; 3]$：$[2]$，1 个区块； 11. $[3; 4]$：$[2] + [4]$，2 个区块； 12. $[3; 5]$：$[2] + [4] + [5]$，3 个区块； 13. $[4; 4]$：$[4]$，1 个区块； 14. $[4; 5]$：$[4] + [5]$，2 个区块； 15. $[5; 5]$：$[5]$，1 个区块； 总和为 $1 + 2 + 2 + 3 + 4 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 29$。 由 ChatGPT 4.1 翻译