P12667 [KOI 2023 Round 2] 傻瓜锁

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

KOI 国即将举办一场“快速解锁比赛”。你作为参赛者，正在练习解锁的能力。本次比赛所用的锁因为特性特殊，被称为**傻瓜锁**。 傻瓜锁可以用一个由小写英文字母组成的字符串 $S$ 表示。你可以在一次操作中选定 $S$ 中的某个字符，将其修改为**字母表顺序中相邻的字母**。例如，当傻瓜锁的当前状态为 `"ioiaa"` 时，你可以进行以下 8 种操作： - 将第 1 个字符 `'i'` 改为 `'h'`。 - 将第 1 个字符 `'i'` 改为 `'j'`。 - 将第 2 个字符 `'o'` 改为 `'n'`。 - 将第 2 个字符 `'o'` 改为 `'p'`。 - 将第 3 个字符 `'i'` 改为 `'h'`。 - 将第 3 个字符 `'i'` 改为 `'j'`。 - 将第 4 个字符 `'a'` 改为 `'b'`。 - 将第 5 个字符 `'a'` 改为 `'b'`。 傻瓜锁具有如下特性：**当字符串中字符按照字母表升序排列时，锁就被解开了**。也就是说，对于任意的 $i$（$1 \leq i < |S|$），必须有 $S_i \leq S_{i+1}$。 例如，`"aabbcc"`、`"eel"`、`"a"`、`"zzzzz"` 都是升序排列的；而 `"lee"`、`"ccbbaa"`、`"koi"` 则不是升序排列的。 定义一个傻瓜锁当前状态为字符串 $S$ 时，**将其解锁所需的最小操作次数**，称为该字符串 $S$ 的**难度**。你已经在练习如何快速计算 $S$ 的难度。 现在，你打算通过更难的练习方式来提升自己。 初始时，给定傻瓜锁的状态为字符串 $S$，长度为 $N$。接下来，你将接收到 $Q$ 个**更新操作（query）**，每次操作修改 $S$ 中的某一位字符。每次操作由一个整数 $i$（$1 \leq i \leq N$）和一个小写字母 $c$ 组成，表示将 $S$ 中第 $i$ 个字符改为 $c$。这些更新操作需要**按顺序依次应用**。 你的任务是：首先输出初始字符串 $S$ 的难度，之后每处理完一个更新操作，输出更新后字符串 $S$ 的难度。

第一行输入字符串 $S$。 第二行输入整数 $Q$，表示操作数量。 若 $Q > 0$，接下来 $Q$ 行，每行输入两个值 $i\ c$，表示将 $S$ 的第 $i$ 个字符改为字符 $c$，两者用空格分隔。

总共需输出 $Q + 1$ 个整数，依次为： - 第 1 行输出初始字符串 $S$ 的难度； - 若 $Q > 0$，接下来的 $Q$ 行，依次输出每次更新操作后当前字符串 $S$ 的难度。

**限制条件** - $S$ 由小写英文字母组成。 - $S$ 的长度 $N$ 满足 $1 \leq N \leq 100\,000$。 - $0 \leq Q \leq 100\,000$。 - $1 \leq i \leq N$。 - $c$ 为小写英文字母，且保证 $c$ 不等于更新前 $S$ 的第 $i$ 个字符。 - “小写英文字母”指的是 `"abcdefghijklmnopqrstuvwxyz"`。 **子任务** 1. （7 分）$Q = 0$，$N \leq 5\,000$，且 $S$ 仅由 `'a'`、`'b'` 组成。 2. （6 分）$Q \leq 10$，$S$ 仅由 `'a'`、`'b'` 组成，更新后依然保持只含 `'a'`、`'b'`。 3. （5 分）$Q \leq 10$，$S$ 仅由 `'a'`、`'b'`、`'c'` 组成，更新后依然保持只含这三种字符。 4. （4 分）$Q \leq 10$，$S$ 仅由 `'a'`、`'b'`、`'c'`、`'d'`、`'e'` 组成，更新后依然保持如此。 5. （3 分）$Q \leq 10$。 6. （12 分）$S$ 仅由 `'a'`、`'b'` 组成，更新后依然保持如此。 7. （10 分）$S$ 仅由 `'a'`、`'b'`、`'c'` 组成，更新后依然保持如此。 8. （8 分）$S$ 仅由 `'a'`、`'b'`、`'c'`、`'d'`、`'e'` 组成，更新后依然保持如此。 9. （45 分）无附加限制。 翻译由 ChatGPT-4o 完成