牛客IOI周赛16-提高组 - 小L扔垃圾

题意

有一排垃圾，垃圾有三种 R,W,D。取一段连续的垃圾，并且 W 与 D 的数量相同，令最大能取到的垃圾数量为 ans。求最初的 ans，和在最前/最后放指定垃圾后的 ans。

算法（）

若答案有更新，则当前放的垃圾为这一段的一端。考虑这一段最大长度，将 R,W,D 分别视作 ，则要求这一段和为 。进行前缀和与后缀和处理，则可以视作与当前的前缀/后缀和相等的最远的位置。

令 表示前缀和为 的最前位置，新增垃圾处的前缀和为 ，则当前新的答案为 当前位置-。

对于 的维护，在最后放垃圾时，直接更新 ；在最前方垃圾是，先将整个 向左/向右移动一个下标（ 或 ），在更新 或 。

可以用数组+差分维护，移动时直接移动差分量即可。