← 返回题目列表

Codeforces · 1609/E

E. 遗忘者威廉

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

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

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

如果可以通过删除一些字符而不改变剩余字符的顺序从 $$$y$$$ 获得 $$$x$$$,则字符串 $$$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 12
aaabccccc
4 a
4 b
2 b
5 a
1 b
6 b
5 c
2 a
1 a
5 a
6 b
7 b

输出 #1

0
1
2
2
1
2
1
2
2
2
2
2

注意

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

1. $$$s = $$$"aaaaccccc"。在这种情况下,字符串不包含“abc”作为子序列,并且不需要替换。
2. $$$s = $$$"aaabccccc"。在这种情况下,可以执行 1 次替换以获得字符串 $$$s = $$$"aaaaccccc"。该字符串不包含“abc”作为子序列。
3. $$$s = $$$"ababccccc"。在这种情况下,可以执行 2 次替换来得到,例如字符串 $$$s = $$$aaaacccccc"。该字符串不包含“abc”作为子序列。
4. $$$s = $$$"ababacccc"。在这种情况下,可以执行 2 次替换来获取字符串 $$$s = $$$"aaaaacccc"。该字符串不包含“abc”作为子序列。
5. $$$s = $$$"bbabacccc"。在这种情况下,可以执行 1 次替换以获得字符串 $$$s = $$$"bbacacccc"。该字符串不包含“abc”作为子序列。
6. $$$s = $$$“bbababccc”。在这种情况下,可以执行 2 次替换来获取字符串 $$$s = $$$"bbacacccc"。该字符串不包含“abc”作为子序列。
7. $$$s = $$$“bbabcbccc”。在这种情况下,可以执行 1 次替换以获得字符串 $$$s = $$$"bbcbcbccc"。该字符串不包含“abc”作为子序列。
8. $$$s = $$$“baabcbccc”。在这种情况下,可以执行 2 次替换来获取字符串 $$$s = $$$"bbbbbcbccc"。该字符串不包含“abc”作为子序列。
9. $$$s = $$$“aaabcbccc”。在这种情况下,可以执行 2 次替换来获取字符串 $$$s = $$$"aaacccccc"。该字符串不包含“abc”作为子序列。
10. $$$s = $$$“aaababccc”。在这种情况下,可以执行 2 次替换来获取字符串 $$$s = $$$"aaacacccc"。该字符串不包含“abc”作为子序列。
11. $$$s = $$$“aaababccc”。在这种情况下,可以执行 2 次替换来获取字符串 $$$s = $$$"aaacacccc"。该字符串不包含“abc”作为子序列。
12. $$$s = $$$"aaababbcc"。在这种情况下,可以执行 2 次替换来获取字符串 $$$s = $$$"aaabbabbbb"。该字符串不包含“abc”作为子序列。