Count ABC Again

题目描述

你得到一个长度为 $N$ 的字符串 $S$。你还得到 $Q$ 个查询，需要按顺序处理。 第 $i$ 个查询如下：

给定一个整数 $X_i$ 和一个字符 $C_i$，将 $S$ 的第 $X_i$ 个字符替换为 $C_i$。然后，输出字符串 $ABC$ 在 $S$ 中作为子串出现的次数。

这里，子串 指通过从开头删除零个或多个字符并且从结尾删除零个或多个字符从 $S$ 中得到的字符串。
例如，$ab$ 是 $abc$ 的一个子串，但 $ac$ 不是 $abc$ 的子串。

输入格式

输入从标准输入给出，格式如下： $N$ $Q$ $S$ $X_1$ $C_1$ $X_2$ $C_2$ $\vdots$ $X_Q$ $C_Q$

输出格式

输出 $Q$ 行。 第 $i$ 行 $(1 \le i \le Q)$ 应该包含第 $i$ 个查询的答案。

7 4
ABCDABC
4 B
3 A
5 C
4 G

2
1
1
0

3 3
ABC
1 A
2 B
3 C

1
1
1

15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

0
0
0
0
1
1
2
2
1
1

提示

$3 \le N \le 2 \times 10^5$ $1 \le Q \le 2 \times 10^5$ $S$ 是一个长度为 $N$ 的由大写英文字母组成的字符串。 $1 \le X_i \le N$ $C_i$ 是一个大写英文字母。处理每个查询后，$S$ 变为如下。

第一个查询之后：$S=$ $ABCBABC$。在这个字符串中，$ABC$ 作为子串出现了两次。 第二个查询之后：$S=$ $ABABABC$。在这个字符串中，$ABC$ 作为子串出现了一次。 第三个查询之后：$S=$ $ABABCBC$。在这个字符串中，$ABC$ 作为子串出现了一次。 第四个查询之后：$S=$ $ABAGCBC$。在这个字符串中，$ABC$ 作为子串出现了零次。
存在在处理某个查询时 $S$ 不发生变化的情况。

标签: AtCoder|abc372C

来源

AtCoder|abc372C