【P8367】[LNOI2022] 盒 胡扯

本文应该是要配图的，但是笔者懒得搞，建议是找一张草稿纸画画就懂了。

试图用更形象的角度分析问题。

首先我们所求的式子是：

其中 $pre$ 为前缀和。

拆掉绝对值，先只计算 $j < pre$，然后 reverse 整个数组再做一遍。也就是求：

发现这个式子后半部分有点类似组合数行前缀和的问题，考虑用那个莫队做法类似的方式，每次移动 $i \leftarrow i+1$ 或 $pre \leftarrow pre+1$，维护后面一坨的值，总共要移动 $O(n+S)$ 次。

考虑怎么移动。

将 $b$ 数组一一对应到在一张大小为 $n\times(S+1)$ 的网格图上的一条从左上角走到右下角的路径，记左上角为 $(1,0)$，右下角为 $(n,S)$

那么原式就相当对每一条路径，考虑他走过的那一条 $(i,j)$ 到 $(i+1,j)$ 的边，会产生 $max(0,pre-j)$ 的贡献。

先考虑一个简单的形式，也就是贡献为 $[pre > j]$，那么考虑当 $pre \leftarrow pre+1$ 时，增加的贡献显然就是经过 $(i,pre)$ 到 $(i+1,pre)$ 这条边的路径数量，而当 $i\leftarrow i+1$ 时，考虑有多少路径贡献发生变化，显然这条路径经过 $(i,j)$ 到 $(i+1,j)(j < pre)$ 而且经过了 $(i+1,k)$ 到 $(i+2,k)(j \ge pre)$。在纸上比划一下，发现这条路径等价于一定经过 $(i+1,pre-1)$ 到 $(i+1,pre)$。

于是我们解决了这个更简单的形式。考虑原本的形式，记为 $v1$，当 $pre \leftarrow pre+1$ 是，所有经过 $(i,j)$ 到 $(i+1,j)(j \le pre)$ 的路径贡献全部增加 $1$，这样的路径的条数我们上一段就求出来了，记为 $v2$。当 $i \leftarrow i+1$ 时，发现每经过一条 $(i+1,j)$ 到 $(i+1,j+1)(j < pre)$ 的边，贡献就会 $-1$，那么枚举这样的一条边，可以把代数形式写出来，也可以视选择这条产生贡献的边为一条向下的边，都可以转化为上一段的形式，这里就不再赘述。这个贡献的变化量记为 $v3$。在移动 $i$ 和 $pre$ 的时候同时维护 $v1,v2,v3$ 即可。