Luogu4786 [BalkanOI2018]Election

题意 ： 一个长度为 的字符串 ，它仅由 C 和 T 两种字母组成。

每次询问给出 和 ，求至少在 中删除多少个字符，才能保证：对于其每一个前缀和后缀，其 C 的数量都不小于 T 的数量。

，时限 。

---

感谢 @热言热语 的指导。

考虑如何回答单组询问。

将 C 的权值赋为 ，T 的权值赋为 ，合法等价于使得前后缀和均非负。

不难发现，我们只会删除 T。

从前往后考虑，若前缀和为负，则删除当前字符 （一定为 T）。

再从后往前考虑，若后缀和为负，则删除当前字符 （一定为 T）。

不难发现，第一次扫描中删除了合法的尽量靠后的 T，最有利于第二次扫描，这个贪心是正确的。

---

考虑如何刻画我们删除的 T。

记 为前缀和， 为后缀和。

第一次扫描中删除的 T 即为 第一次为 的位置，删除的总个数即为 。

记 为第一次扫描（删除）后的后缀和。

第而次扫描中删除的 T 即为 第一次为 的位置，删除的总个数即为 。

考虑如何表示 。 对于 ，其前面在第一轮中遭到的删除次数为 ，则后面（含）遭到的删除次数为

于是

综上 ：

这相当于找出两个不交的前缀后缀，使得和最小。取补集，也相当于找出一个区间使得和最大。

线段树维护区间最大子段和即可。复杂度 。