[ABC407F] Sums of Sliding Window Maximum 题解

一眼题啊。设 左侧第一个不比它小的数的位置为 ，它右侧第一个比它大的数的位置为 。（这样可以保证既不漏算又不重复计算。）那么对于 ，它可能作为最大值的极长区间显然是 。这个区间又被 分为左右两段。设两段中较短的一段长度为 ，较长一段长度为 ，总长度为 。那么 可以带来以下贡献：

• ；

• ；

• 。

将第三组式子拆为：

• 。

于是维护两个差分数组即可。第一个差分数组 维护的实际值就是 ，第二个差分数组 维护的实际值是 。

于是就做完了。

提交记录。