题解 P4786 【[BalkanOI 2018 Day1]Election】

热言热语 · 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)，取决于你使用的数据结构。