[ABC407F] Sums of Sliding Window Maximum 题解

Getaway_Car · 2025-05-26 21:01:17 · 题解

一眼题啊。设 a_i 左侧第一个不比它小的数的位置为 lft_i，它右侧第一个比它大的数的位置为 rgt_i。（这样可以保证既不漏算又不重复计算。）那么对于 a_i，它可能作为最大值的极长区间显然是 (lft_i, rgt_i)。这个区间又被 a_i 分为左右两段。设两段中较短的一段长度为 mn = \min\{i - lft[i], rgt[i] - i\}，较长一段长度为 mx = \max\{i - lft[i], rgt[i] - i\}，总长度为 len = rgt_i - lft_i + 1。那么 a_i 可以带来以下贡献：

将第三组式子拆为：

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

于是就做完了。

提交记录。