[ABC407F] Sums of Sliding Window Maximum 题解

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

将第三组式子拆为：

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