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函数为${\sum }_{l=1}^n{\sum }_{r=l}^{n}g(l,r)$

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

思路

先来看看全部相等的元素的数组，它的h函数的值。
那么$$h=\sum _{l=1}^n\sum _{r=l}^{n}g(l,r)=\sum _{l=1}^n\sum _{r=l}^{n}1=n\ast (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);
1
2
3
4
5
6

类似地，我们去计算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);
1
2
3
4
5

这里注意防爆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 < n; ++i) {
		update(i, 1LL);
	}
}
void cal(int pos, int x) {
	update(pos-1, -1LL);
	update(pos, -1LL);
	a[pos] = x;
	update(pos-1, 1LL);
	update(pos, 1LL);
	
	printf("%lld\n", res);
}
void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	a[0] = a[n+2] = 0;
	init();
	int pos, x;
	while (m--) {
		scanf("%d%d", &pos, &x);
		cal(pos, x);
	}
}
int main() {
	int t;
	t = 1;
	while (t--) {
		solve();
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

最后

觉得文章不错的话，weixin gongzhonghao 关注下 对方正在debug，一起快乐刷题吧~