P9334

lsj2009 · 2025-09-02 13:35:55 · 题解

注意到小段长度 >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}))。