题解：CF570C Replacement

原题链接

• 洛谷 CF570C Replacement

题意简述

给定长度为 $n$ 的字符串，包含 . 和小写字母，进行 $m$ 次操作，每次修改一个字符，并询问将所有连续 . 转化为单个 . 所需的次数。

解题思路

设字符串中有 $k$ 个连续的 . 子串，长度分别为 $a_i$。每个子串需要 $a_i - 1$ 次转化，总转化次数为：

$$\sum_{i=1}^k (a_i - 1) = \left( \sum_{i=1}^k a_i \right) - k$$

注意到，$\sum_{i=1}^k a_i$ 为字符串中所有 . 的总数，在每次操作中，判断是否将某个 . 替换为字母或字母替换为 .，即可更新 . 的数量。

对于每次操作分类讨论，维护 . 子串数量：

1. 将 . 替换为字母：如果左右两边都是字母，则 . 子串数量减少 $1$，转化次数加 $1$；如果左右两边都是 .，则 . 子串数量增加 $1$，转化次数减少 $1$。
2. 将字母替换为 .：如果左右两边都是字母，则 . 子串数量增加 $1$，转化次数减少 $1$；如果左右两边都是 .，则 . 子串数量减少 $1$，转化次数增加 $1$。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=300005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		char f;
		cin>>f;
		a[i]=f=='.';
		if(a[i]&&a[i-1])ans++;
	}
	while(m--)
	{
		int x;
		char f;
		cin>>x>>f;
		int y=f=='.';
		if(a[x]!=y)
		{
			a[x]=y;
			ans+=(a[x-1]+a[x+1])*(y*2-1);
		}
		cout<<ans<<'\n';
	}
	return 0;
}