题解：P4786 [BalkanOI 2018] Election

· · 题解

贪心很简单，无非就是将 C 替换成 1，将 T 替换成 -1 并存到数组 a 中，然后再得到两个数组 pre_i 和 suf_j 分别表示前缀和和后缀和，再在区间 [l,r] 内从前往后扫或者从后往前扫找到需要删除的字符即可。

首先从前往后扫。显然的，当 pre_i 为负数时，此时区间内 C 的数量必定小于 T 的数量，且当前字符为 T，于是使得 a_i\gets0，即删除这个字符。最后操作次数为 -\min\{pre_i\}。从后往前扫同理，得到 -min\{suf_j\}，只不过有部分字符在从前先往后扫时已经被删除，所以最终操作次数应为 -min\{suf_j\}+min\{pre_i\}。最后必定满足 \sum_{i<k<j}a_k\ge0。

我们发现一个最大子段和的所有前缀与后缀和也大于等于 0，那么区间 (i,j) 必定为一个最大子段和。

建一个线段树同时维护一个区间的长度 S 和最大子段和长度 Z，答案便是 S-Z。

参考代码