别看这是道黄题，其实想清楚了还是很简单的。
思路
1. 如何算出答案
对于字符串 $S = \overline{s_1 s_2 \dots s_n}, T = S$，想让 $T = \overline{s_1 s_1 s_2 s_2 \dots s_n s_n}$，最简单的方法就是用 $n$ 次操作，这想必大家都能想到。
更进一步，我们发现连续的相同字符可以视作一个整体，只需要一次操作，就好比字符串 $\texttt{aaa}$ 只用一次操作就能解决。
对于这种连续的字符，我们称之为一个“块”。使用这种方法，我们所求的最小操作次数就应该是 $S$ 中“块”的最小个数（即不存在两个连续且字符相同的“块”），我们设其为 $x$。
同时，我们还可以把相邻的两个“块”一起处理，只需要把这两个“块”连接起来，放在中间就可以。如 $\texttt{aaabbccddd}$，我们只需要把 $\texttt{aaabb}$ 插入到最后一个 $\texttt{a}$ 的后面，把 $\texttt{ccddd}$ 插入到最后一个 $\texttt{c}$ 的后面即可。这样，最后的答案就是 $\lceil \dfrac{x}{2} \rceil$。
2. 如何维护
由于 $S$ 长度不短，所以每次计算答案时现找答案是行不通的。
我们一开始先遍历一遍，找出 $x$（“块”的最小个数）。然后我们在每次修改时只需要判断一下：
- 是否和左边部分原来是一个“块”，但是修改后分成了两个“块”？如是，$x + 1$；
- 是否和右边部分原来是一个“块”，但是修改后分成了两个“块”？如是，$x + 1$；
- 是否和左边部分原来不是一个“块”，但是修改后合成了新的“块”？如是，$x - 1$；
- 是否和右边部分原来不是一个“块”，但是修改后合成了新的“块”？如是，$x - 1$。
代码
#include <cstdio>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define elif else if
int q;
string s;
char _s[3000005];//scanf读入快一点
int main()
{
scanf("%d %s", &q, _s);
s = _s;
int cnt = 1;
for (int i = 1; i < s.size(); i++)//先统计一下初始有多少“块”
if (s[i] != s[i - 1])
cnt++;
printf("%d\n", int(ceil(cnt / 2.0)));//一定要记得转int
int p;
char c;
for (int i = 1; i <= q; i++)
{
scanf("%d %c", &p, &c);
p--;//下标不一样，string下标从0开始
if (p != 0 && s[p] == s[p - 1] && c != s[p - 1])//情况1
cnt++;
if (p != s.size() - 1 && s[p] == s[p + 1] && c != s[p + 1])//情况2
cnt++;
if (p != 0 && s[p] != s[p - 1] && c == s[p - 1])//情况3
cnt--;
if (p != s.size() - 1 && s[p] != s[p + 1] && c == s[p + 1])//情况4
cnt--;
//一定要注意判断边界
s[p] = c;
printf("%d\n", int(ceil(cnt / 2.0)));
}
return 0;
}提交记录：赛时 R98904527 | 赛后 R99301657。