← 返回题目列表

Codeforces · 1609/B

B. 警惕的威廉

中文机器翻译题面 查看原题

在成为一名成功的交易员之前,威廉获得了大学学位。在他的教育过程中,发生了一个有趣的情况,之后威廉开始更加专心地听作业。以下是家庭作业的正确正式描述:

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符“a”、“b”和“c”。存在格式为 ($$$pos, c$$$) 的 $$$q$$$ 查询,表示将 $$$s$$$ 位置 $$$pos$$$ 处的元素替换为字符 $$$c$$$。每次查询后,您必须输出字符串中必须替换的最少字符数,以便字符串不包含字符串“abc”作为子字符串。字符的有效替换是将其替换为“a”、“b”或“c”。

字符串 $$$x$$$ 是字符串 $$$y$$$ 的子字符串,如果 $$$x$$$ 可以通过删除开头的几个(可能是零个或全部)字符和结尾的几个(可能是零个或全部)字符从 $$$y$$$ 获得。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \le n, q \le 10^5)$$$,分别表示字符串长度和查询次数。

第二行包含字符串$$$s$$$,由字符“a”、“b”和“c”组成。

接下来的 $$$q$$$ 行分别包含整数 $$$i$$$ 和字符 $$$c$$$ $$$(1 \le i \le n)$$$、索引和字符串中新项目的值。保证字符的 $$$c$$$ 值为“a”、“b”或“c”。

输出

对于每个查询输出,必须替换的最小字符数,以便字符串不包含“abc”作为子字符串。

示例

输入 #1

9 10
abcabcabc
1 a
1 b
2 c
3 a
4 b
5 c
8 a
9 b
1 c
4 a

输出 #1

3
2
2
2
1
2
1
1
1
0

注意

让我们考虑一下每次查询后字符串的状态:

1. $$$s =$$$“abcabcabc”。在这种情况下,可以执行 $$$3$$$ 替换以获得字符串 $$$s =$$$ "bbcaccabb"。该字符串不包含“abc”作为子字符串。
2. $$$s =$$$“bbcabcabc”。在这种情况下,可以执行 $$$2$$$ 替换以获得字符串 $$$s =$$$ "bbcbbbcbbc"。该字符串不包含“abc”作为子字符串。
3. $$$s =$$$“bccabcabc”。在这种情况下,可以执行 $$$2$$$ 替换以获得字符串 $$$s =$$$ "bccbbbcbbc"。该字符串不包含“abc”作为子字符串。
4. $$$s =$$$“bcaabcabc”。在这种情况下,可以执行 $$$2$$$ 替换以获得字符串 $$$s =$$$ "bcabbbcbbc"。该字符串不包含“abc”作为子字符串。
5. $$$s =$$$“bcabbcabc”。在这种情况下,可以执行 $$$1$$$ 替换以获得字符串 $$$s =$$$ "bcabbcabb"。该字符串不包含“abc”作为子字符串。
6. $$$s =$$$“bcabccabc”。在这种情况下,可以执行 $$$2$$$ 替换以获得字符串 $$$s =$$$ "bcabbcabb"。该字符串不包含“abc”作为子字符串。
7. $$$s =$$$“bcabccaac”。在这种情况下,可以执行 $$$1$$$ 替换以获得字符串 $$$s =$$$ "bcabbcaac"。该字符串不包含“abc”作为子字符串。
8. $$$s =$$$“bcabccaab”。在这种情况下,可以执行 $$$1$$$ 替换以获得字符串 $$$s =$$$ "bcabbcaab"。该字符串不包含“abc”作为子字符串。
9. $$$s =$$$“ccabccaab”。在这种情况下,可以执行 $$$1$$$ 替换以获得字符串 $$$s =$$$ "ccabbcaab"。该字符串不包含“abc”作为子字符串。
10. $$$s =$$$“ccaaccaab”。在这种情况下,字符串不包含“abc”作为子字符串,并且不需要替换。