题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

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$ 的难度。

ababba
5
1 b
3 b
2 a
2 b
5 a

2
2
1
2
1
2

acabed
5
1 c
2 a
3 d
4 c
5 a

3
4
3
5
4
5

acaykp
6
1 c
2 a
5 a
6 k
3 p
4 c

16
16
16
26
26
31
17

zaire
1
5 r

38
25

提示

限制条件

• $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 完成