自动搬运

查看原文

来自洛谷，原作者为

	热言热语 try { hard } catch (dream) {} finally { AFO } —— PinkRabbit 是信仰

搬运于2025-08-24 22:03:37，当前版本为作者最后更新于2020-04-26 08:34:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于这类题（类似括号匹配），按照套路可以把 C 看成 $1$，把 T 看成 $-1$，然后转化题意。

• 对于子串 $S$，我们按上述方法可以得到一个序列。

• 这样，限制条件就转变为序列的每一个前缀和以及后缀和都非负。

• 而对于删除操作，显然要删除字符只可能删去 T，而删除一个字符可以看成把序列中这个位置改成 $0$。

先考虑一个简单的贪心：

• 从左到右扫描整个序列，如果前缀和为负就把这个位置的 T 删掉（显然这个位置上一定是 T）；

• 再倒着扫描一遍，如果后缀和为负同样把这个位置的 T 删掉。

• 由于第一遍扫描时已经使被删掉的 T 的位置尽量靠后，这样能最大限度地影响到后缀和，由此可以确保贪心的正确性。

• 这样，我们就有了一个 $O(nq)$ 的做法，对每次询问暴力即可。

不妨换个方式考虑这个贪心。

下面为便于叙述，我们记位置 $p$ 处的前缀和与后缀和分别为 $\mathrm{pre}_p$ 和 $\mathrm{suf}_p$，整个序列的最小前缀、后缀和分别为 $\mathrm{pre}_{\min}$ 和 $\mathrm{suf}_{\min}$。

• 第一遍扫描就是对于前缀和 $\mathrm{pre}_p$ 第一次变为 $-1, -2, -3, \ldots$ 的每个位置 $p$ 进行删除操作，把 $[1,p]$ 的后缀和全部加上 $1$，总的操作次数为最小前缀和的相反数 $-\mathrm{pre}_{\min}$；

• 第二遍扫描就是对于后缀和 $\mathrm{suf}'_q$ 第一次变为 $-1, -2, -3, \ldots$ 的每个位置 $q$ 进行删除操作，总的操作次数为最小后缀和的相反数 $-\mathrm{suf}'_{\min}$。注意这里的序列是第一遍扫描后的，所以 $\mathrm{suf}$ 的右上角加了一撇。

显然，$\mathrm{pre}_{\min}$ 是容易求得的（虽然最后它被消掉了），现在我们尝试求出 $\mathrm{suf}'_{\min}$。

• 考虑位置 $q$ 在第一遍扫描时后缀和被加 $1$ 的次数。

  根据前面的分析，在总共的 $-\mathrm{pre}_{\min}$ 次加 $1$ 中，没有加到位置 $q$ 的次数就是在 $q$ 之前前缀和第一次变为 $-1, -2, -3, \ldots$ 的位置个数，也就是 $q$ 之前的最小前缀和的相反数，即 $-\min_{p \lt q} \mathrm{pre}_p$。

  于是，位置 $q$ 后缀和被加 $1$ 的次数即为 $\min_{p \lt q} \mathrm{pre}_p - \mathrm{pre}_{\min}$。

• 那么，第一遍扫描后位置 $q$ 的后缀和变成了 $\mathrm{suf}'_q = \mathrm{suf}_q + \min_{p \lt q} \mathrm{pre}_p - \mathrm{pre}_{\min}$。

• 根据前面的结论，总的操作次数即为：

  $-\mathrm{pre}_{\min}-\mathrm{suf}'_{\min} = -\min (\mathrm{pre}_{\min} + \mathrm{suf}'_q) = -\min_{p \lt q} (\mathrm{pre}_p+\mathrm{suf}_q)$

• 冷静一下可以发现，这玩意用人话说就是：找到一对不重合的前缀与后缀，使得它们的和最小，答案即为这个和的相反数。

  换一个方面考虑，用「总和」减去「一对不重合的前缀与后缀的和」得到的是「夹在这对前缀与后缀之间的连续子段的和」，所以答案可以等价地表述为「区间的最大连续子段和」减去「区间和」。

• 利用线段树 / 平衡树 / 猫树 / 你能想到的任何数据结构维护即可，时间复杂度 $O(n + q \log n)$ 或 $O(n \log n + q)$，空间复杂度 $O(n)$ 或 $O(n \log n)$，取决于你使用的数据结构。