C. Monoblock（思维/计数）

题目

题意

定义一个数组，定义它 相等连续段的个数 如1,2,2,1，相等连续段有[1],[2,2],[1]，共3个 如2,2,2,1，相等连续段有[2,2,2],[1]，共2个

给定一个数组a，定义g(l,r)为，子数组中a[l],a[l+1],…,a[r]，相等连续段的个数。 定义h函数为 ∑ l = 1 n ∑ r = l n g ( l , r ) \sum_{l=1}^n\sum_{r=l}^n g(l,r) ∑l=1n​∑r=ln​g(l,r)

给定m次操作，每次修改数组第i个位置的值为x。求每次操作后的数组的h函数的值。

思路

先来看看全部相等的元素的数组，它的h函数的值。 那么 h = ∑ l = 1 n ∑ r = l n g ( l , r ) = ∑ l = 1 n ∑ r = l n 1 = n ∗ ( n + 1 ) / 2 h=\sum_{l=1}^n\sum_{r=l}^n g(l,r)=\sum_{l=1}^n\sum_{r=l}^n 1 = n*(n+1)/2 h=l=1∑n​r=l∑n​g(l,r)=l=1∑n​r=l∑n​1=n∗(n+1)/2

对于一个元素全部相等的区间，它的g函数值为1， 如果修改一个元素，且该元素与其相邻元素不等时，那么该区间的g函数值会加1。

1. 计算初始的h函数值。

我们把数组初始看成n个a[1]。 此时h函数为n*(n+1)/2。

接着把第二个数修改为a[2]，此时，如果a[2]!=a[1]，那么所有包含a[2]和a[1]的区间，g函数都会加1。

void update(int pos, ll d)
if (a[pos] != a[pos+1]) {
	res += d * (n - pos) * pos;
}

update(1, 1);

类似地，我们去计算a[3],a[4],…a[n]，即可得到初始的h函数值。

2. 计算每次更新后的数组的h函数值。

每次更新第i个元素，那么它会影响a[i-1]与a[i]，a[i]与a[i+1]是否相等。 我们需要减去原来的贡献，加上新变化后的贡献。

update(pos-1, -1LL);
update(pos, -1LL);
a[pos] = x;
update(pos-1, 1LL);
update(pos, 1LL);

这里注意防爆int，转换为long long做计算

代码

#include 
using namespace std;
#define ll long long
const int maxn = 200010;

int n, m;
int a[maxn];
ll res;

void update(int pos, ll d) {
	if (a[pos] != a[pos+1]) {
		res += d * (n - pos) * pos;
	}
}
void init() {
	res = 1LL * (1 + n) * n / 2;
	for (int i = 1; i