牛客IOI周赛16-提高组 - 小L扔垃圾
小L扔垃圾
https://ac.nowcoder.com/acm/contest/5388/B
题意
有一排垃圾，垃圾有三种 R,W,D。取一段连续的垃圾，并且 W 与 D 的数量相同，令最大能取到的垃圾数量为 ans。求最初的 ans，和在最前/最后放指定垃圾后的 ans。
算法（&preview=true)
）
若答案有更新，则当前放的垃圾为这一段的一端。考虑这一段最大长度，将 R,W,D 分别视作 ，则要求这一段和为
。进行前缀和与后缀和处理，则可以视作与当前的前缀/后缀和相等的最远的位置。
令 表示前缀和为
的最前位置，新增垃圾处的前缀和为
，则当前新的答案为 当前位置-
。
对于 的维护，在最后放垃圾时，直接更新
；在最前方垃圾是，先将整个
向左/向右移动一个下标（
或
），在更新
或
。
可以用数组+差分维护，移动时直接移动差分量即可。
投递蚂蚁集团等公司10个岗位 >
