CF1609E William The Oblivious
题目描述
在成为一名成功的交易员之前，William 获得了大学学位。在他的求学过程中，发生了一件有趣的事情，从那以后，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$，分别表示要替换的位置和新的字符，满足 $1 \le i \le n$，$c$ 仅为 "a"、"b" 或 "c"。
输出格式
对于每个操作，输出一个整数，表示最少需要替换多少个字符，才能使字符串中不包含 "abc" 作为子序列。
说明/提示
考虑每次操作后字符串的状态：
1. $s = $ "aaaaccccc"。此时字符串不包含 "abc" 作为子序列，无需替换。
2. $s = $ "aaabccccc"。此时只需替换 1 个字符，例如变为 $s = $ "aaaaccccc"，此时不包含 "abc" 作为子序列。
3. $s = $ "ababccccc"。此时只需替换 2 个字符，例如变为 $s = $ "aaaaccccc"，此时不包含 "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 = $ "bbbbcbccc"，此时不包含 "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 = $ "aaababbbb"，此时不包含 "abc" 作为子序列。
由 ChatGPT 4.1 翻译