思路

根据题意我们不难看出，求一个区间的块的数量即求区间内 \(a_i\neq a_{i-1}\) 的数量，如果直接枚举每个区间的话，时间复杂度是 \(\mathcal O(n^2)\) 显然这样做是不行的，但是我们可以考虑每一个 \(a_i\neq a_{i-1}\) 对答案产生的贡献，即有多少个区间包含 当前的 \(i\) 和 \(i-1\) 根据简单的组合数学知识和乘法原理，我们只需考虑在 \(1\) 到 \(i-1\) 中选一个点作为区间左端点的方案数，乘上在 \(i\) 到 \(n\) 之间选取一个点作为区间右端点的方案数，这样算出来的结果为该 \(a_i\neq a_{i-1}\) 产生的贡献，再加上序列的所有子区间数量，即 \(\dfrac{n\times (n+1)}{2}\) 即可。

代码如下

for (int i = 2; i <= n; i++) {

	ans += (i - 1) * (n - i + 1) * (int)(a[i] != a[i - 1]);
}

ans += (n * (n + 1)) / 2;

每次修改的时候也是类似的做法，考虑每次修改后，修改的点 \(i\) 修改之前是否和 \(i-1\) 和 \(i+1\) 相等，修改之后是否和 \(i-1\) 和 \(i+1\) 来考虑每次修改对答案产生的影响，若修改前相等修改后不相等则在原答案的基础上加上修改后产生的贡献，若修改前不相等修改后相等则减去原先对答案产生的贡献。具体细节看代码。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, f[1000100], a[100010], ans, b[100010];

signed main() {
	scanf("%lld%lld", &n, &m);

	for (int i = 1; i <= n; i++) {

		scanf("%lld", &a[i]);
	}

	for (int i = 2; i <= n; i++) {

		ans += (i - 1) * (n - i + 1) * (int)(a[i] != a[i - 1]);
	}

	ans += (n * (n + 1)) / 2;

	while (m--) {
		int op, x;
		scanf("%lld%lld", &op, &x);

		if (op > 1) {
			if (a[op - 1] == x && a[op - 1] != a[op]) {
				ans -= (op - 1) * (n - op + 1);
			} else if (a[op - 1] != x && a[op - 1] == a[op]) {
				ans += ((op - 1) * (n - op + 1));
			}
		}

		if (op <= n - 1) {
			if (x == a[op + 1] && a[op + 1] != a[op]) {
				ans -= op * (n - op);
			} else if (a[op] == a[op + 1] && a[op + 1] != x) {
				ans += (op * (n - op));
			}
		}

		a[op] = x;
		printf("%lld\n", ans);
	}

	return 0;
}