P9334

注意到小段长度 $>1$ 肯定不优，直接记 $f_i$ 为 $[i,i]$ 是一个小段，在 $\le i$ 的前缀划分的最大段数，暴力是 $\mathcal{O}(n^2)$ 的，可以发现转移来的 $f_j$ 是一个前缀再加上 $\mathcal{O}(\log{V})$ 个零散点（证明和后文的一个结论一致，这里略去），故可以做到 $\mathcal{O}(n\log{V})$。但是这连不带修、区间询问都做不了！

我们肯定希望这个 dp 数组有什么更好的性质，比如……递增？修改 $f_i$ 定义为 $\le i$ 的前缀划分最大段数，姑且认为 $i$ 单成一段（否则并到前一段上，向 $f_{i-1}$ 取个 max 即可）考虑转移，可以说明条件和上面是一致的，即需 $\sum\limits_{j<k<i}a_k>\max(a_i,a_j)$。可能导致的问题是这个 dp 对应的一个方案是 $[l_1,r_1],[l_2,r_2],[l_3,r_3]$，认为三者分别是大/小/大段，然而却只保证了 $\sum\limits_{l_1\le i\le r_1}a_i>a_{l_2}$ 和 $\sum\limits_{l_3\le i\le r_3} a_i\ge a_{r_2}$，并不必然合法。我们将其映射到一个段数相同的且保证合法的方案：若 $a_{l_2}\le a_{r_2}$，改为 $[l_1,r_1],[l_2,l_2],(l_2,r_3]$，否则改为 $[l_1,r_2),[r_2,r_2],[l_3,r_3]$，修改后任意大段总和不变小，故对于更左、更右的修改仍然可以做到；而当小段在最左/最右段时也有类似处理，不再赘述。

此时我们可以断定，$f_i$ 肯定是由某个最大的满足条件的 $j$ 转移来了，因为 $f$ 递增。再要求忽略前缀 max 的转移，$j$ 需满足 $\exist j<p\le i,\sum\limits_{j<k<p}a_k>\max(a_j,a_p)$，有结论：$i-j$ 是 $\mathcal{O}(\log{V})$ 的，一个松的界是 $2\log{V}$。若有 $a_{p-1}>a_p$，此时仅考虑 $a_j$ 对和的限制，则 $p-j\le \log{V}$，因为每遇到一个不合法 $j$ 和就会翻倍；否则 $a_{p-1}\le a_p$，找到极长的这样子的递增段 $[p',i]$，长度也是不大于 $\log{V}$ 的，因为前缀和都是不断翻倍的。

则每次单点修都只会修改一个长度 $\le 2\log{V}$ 区间的 $i$ 对应的 $j$，查询就是从 $r$ 开始不断跳 $j$ 直到跳出 $[l,r]$，看跳了几次。这不就是我们 P3203 弹飞绵羊 吗！由于重算一个 $i$ 的 $j$ 是 $\mathcal{O}(\log{V})$ 的，而 $B=\sqrt{n}\ge 2\log{V}$，故每次修改至多仅重构两个块，总复杂度就是 $\mathcal{O}(n\log{V}+q(\sqrt{n}+\log^2{V}))$。