William The Oblivious 题解

思路

一个字符串不含 abc 子序列，当且仅当扫描它时不能依次匹配到 a、b、c。字符替换的最小次数等于为了阻止这条匹配链所需付出的最小代价。

做法

子任务 1

当 $n\le 10$ 时，每次修改后枚举全部 $3^n$ 个由 a、b、c 构成的目标串。逐个检查目标串是否含 abc 子序列，并统计它与当前串的汉明距离。复杂度为 $O(qn3^n)$。

子任务 2

设状态 $0,1,2$ 分别表示已经匹配了 abc 的长度。对当前字符枚举把它替换为 a、b 或 c，代价为是否发生替换；产生状态 $3$ 的转移被禁止。每次修改后重新扫描整个字符串，复杂度为 $O(nq)$。

满分算法

对一个区间维护六个量：

• a、b、c：删去区间内全部对应字符的代价；
• ab：使区间不含 ab 子序列的最小代价；
• bc：使区间不含 bc 子序列的最小代价；
• abc：使区间不含 abc 子序列的最小代价。

若左右儿子分别为 $L,R$，则

$$\begin{aligned} ab&=\min(L.a+R.ab,\ L.ab+R.b),\\ bc&=\min(L.b+R.bc,\ L.bc+R.c),\\ abc&=\min(L.a+R.abc,\ L.ab+R.bc,\ L.abc+R.c). \end{aligned}$$

单字符结点的三个复合量均为零。一次单点修改只需重算根路径。

正确性证明

以 abc 为例。合并两个相邻区间后，为了不出现跨越分界线的 abc 子序列，只有三种完整且互斥的切分方式：

1. 删除左区间全部 a，右区间自身避免 abc；
2. 左区间避免 ab，右区间避免 bc；
3. 左区间自身避免 abc，删除右区间全部 c。

任意合法结果都属于其中至少一种，三个式子构造出的结果也都合法，因此取最小值恰为最优答案。ab、bc 的合并同理。由叶结点正确和上述合并保持正确，归纳可知根结点的 abc 始终是整个字符串的最优答案。

把被删除字符替换为不会继续相应匹配链的字符即可得到同样代价的替换方案；反过来，任一替换方案中发生替换的位置都可视为删除，因此删除代价与题目要求的替换代价相等。

复杂度

建树复杂度 $O(n)$。每次修改复杂度 $O(\log n)$，总时间复杂度 $O(n+q\log n)$，空间复杂度 $O(n)$。