Educational Codeforces Round 170 (Rated for Div. 2): https://codeforces.com/contest/2025 D题 https://codeforces.com/contest/2025/problem/D

好久没做cf的题了，补一下昨晚的d题

题意

有两个初始值为0的整数S和I, 给定一个长度为n的操作序列r, 一个初始值为0的V

，可以选择S++或者I++
2., 判断是否有 如果成立，V++.
3.,判断是否有, 如果成立，V++.

问V值最大能是多少？

，操作序列中为0的数目为

思路

一系列操作然后求最大值，看着就像动态规划 或者贪心。可以从动态规划入手，可以想到比较直接的状态定义是

表示执行了前个操作，且S的值为的情况下能达到的最大值。转移显然也分三种情况
(1)，
(2),
(3) 其中表示前个操作中为0的数目
初始条件是
最后答案就是
然而直接这样实现复杂度太高需要，这是不可接受的。需要对其进行优化。可以观察到情况（1）需要次操作，而(2)和(3)是,因此需要的是(2)和(3)。
可以观察到 和，二者差别是某个前缀或者后缀整体+1，其余的不变，因此可以将变成一维表示，每次修改前缀或者后缀，而这恰好适合树状数组进行优化。

code

因为只有离线查询，所以用差分数组比树状数组更适合维护区间整体加1。这也是jiangly大佬的做法。

code