CF1609B William the Vigilant

在成为一名成功的交易员之前，William 获得了大学学位。在他的求学过程中，发生了一件有趣的事情，从那以后，William 开始更加认真地听作业要求。以下是作业的正式描述： 给定一个长度为 $n$ 的字符串 $s$，仅由字符 "a"、"b" 和 "c" 组成。有 $q$ 个操作，每个操作为 $(pos, c)$，表示将字符串 $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$，表示将第 $i$ 个字符替换为字符 $c$，其中 $1 \le i \le n$，$c$ 只能是 "a"、"b" 或 "c"。

对于每个操作，输出一个整数，表示最少需要替换多少个字符，才能使字符串中不再包含子串 "abc"。

我们来考虑每次操作后的字符串状态： 1. $s = $ "abcabcabc"。此时可以进行 $3$ 次替换，例如变为 $s = $ "bbcaccabb"。该字符串不包含 "abc" 作为子串。 2. $s = $ "bbcabcabc"。此时可以进行 $2$ 次替换，例如变为 $s = $ "bbcbbcbbc"。该字符串不包含 "abc" 作为子串。 3. $s = $ "bccabcabc"。此时可以进行 $2$ 次替换，例如变为 $s = $ "bccbbcbbc"。该字符串不包含 "abc" 作为子串。 4. $s = $ "bcaabcabc"。此时可以进行 $2$ 次替换，例如变为 $s = $ "bcabbcbbc"。该字符串不包含 "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" 作为子串，无需替换。 由 ChatGPT 4.1 翻译