第 3 题傻瓜锁 (`lock`)

时间限制 1.0 s · 空间限制 256 MB · 120 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 lock.in，输出文件 lock.out。

按照署名—非商业性使用—相同方式共享 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 \le i < |S|$ ），必须有 $S_i \le S_{i+1}$ 。

例如，“aabbcc”、“ee1”、“a”、“zzzzz” 都是升序排列的；而 “lee”、“ccbbaa”、“koi” 则不是升序排列的。

定义一个傻瓜锁当前状态为字符串 $S$ 时，将其解锁所需的最小操作次数，称为该字符串 $S$ 的难度。你已经在练习如何快速计算 $S$ 的难度。

现在，你打算通过更难的练习方式来提升自己。

初始时，给定傻瓜锁的状态为字符串 $S$ ，长度为 $N$ 。接下来，你将接收到 $Q$ 个更新操作（query），每次操作修改 $S$ 中的某一位字符。每次操作由一个整数 $i$ （ $1 \le i \le 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$ 的难度。

样例

样例 1

输入：

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

输出：

样例 2

输入：

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

输出：

样例 3

输入：

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

输出：

样例 4

输入：

zaire
1
5 r

输出：

38
25

提示

限制条件

$S$ 由小写英文字母组成。
$S$ 的长度 $N$ 满足 $1 \le N \le 100\,000$ 。
$0 \le Q \le 100\,000$ 。
$1 \le i \le N$ 。
$c$ 为小写英文字母，且保证 $c$ 不等于更新前 $S$ 的第 $i$ 个字符。
"小写英文字母"指的是 “abcdefghijklmnopqrstuvwxyz”。

子任务

（7 分） $Q = 0$ ， $N \le 5\,000$ ，且 $S$ 仅由 ‘a’、‘b’ 组成。
（6 分） $Q \le 10$ ， $S$ 仅由 ‘a’、‘b’ 组成，更新后依然保持只含 ‘a’、‘b’。
（5 分） $Q \le 10$ ， $S$ 仅由 ‘a’、‘b’、‘c’ 组成，更新后依然保持只含这三种字符。
（4 分） $Q \le 10$ ， $S$ 仅由 ‘a’、‘b’、‘c’、‘d’、‘e’ 组成，更新后依然保持如此。
（3 分） $Q \le 10$ 。
（12 分） $S$ 仅由 ‘a’、‘b’ 组成，更新后依然保持如此。
（10 分） $S$ 仅由 ‘a’、‘b’、‘c’ 组成，更新后依然保持如此。
（8 分） $S$ 仅由 ‘a’、‘b’、‘c’、‘d’、‘e’ 组成，更新后依然保持如此。
（45 分）无附加限制。

翻译由 ChatGPT-4o 完成

第 3 题 傻瓜锁 (lock)