AT_abc407_f [ABC407F] Sums of Sliding Window Maximum 题解

DHT666 · 2025-05-27 15:44:32 · 题解

题意

一个长度为 n 的序列 a_i，求其不同长度连续子序列的最大值和。

思路

如果不用分不同长度怎么做？

可以考虑每个数的贡献，用单调栈求出每个数的贡献区间，直接加和即可。

要分长度怎么做？

假设用单调栈求出当前讨论的 a_i 的贡献区间是 [l_i,r_i]，即在这个区间内、包括了 a_i 的连续子序列都会被 a_i 贡献，我们只要求出每种长度的连续子序列被选了几次，与 a_i 的乘积就是一次对答案的贡献。

其实就是在 [l_i,i] 和 [i,r_i] 中分别选一个数 x 和 y，[x,y] 就会被 a_i 贡献。

我们设 L 为 [l_i,i] 的长度，R 为 [i,r_i] 的长度，len 为 [l_i,r_i] 的长度，p=\min(L,R)，q=\max(L,R)。

现在可以对要贡献的连续子序列的长度 k 分类讨论了。

• 对于 1\le k \le p 的情况，每种 k 会有 k 次被选，这时就是对答案数组的 [1,p] 每个位置加 i，可以差分解决（具体地，先正常差分，然后在统计完做前缀和时，给位置 i 乘上权重 i）。
• 对于 p < k \le q 的情况，每种 k 会有 p 次被选，这时就是对答案数组的 [p+1,q] 每个位置加 p，用典型的差分解决。
• 对于 q < k \le len 的情况，每种 k 会有 len-k+1 次被选，这时就是对答案数组的 [q+1,len] 每个位置加 len-i+1，此时就有些复杂了。分析发现，在区间内，所加的数是每次 -1 的，这时如果我们用差分去解决它，会在差分数组上呈现：加一个数，然后连续一串 -1，这一串 -1 就是在差分数组上区间修改，可以再用一次差分解决它。

基本就讨论完了，还有一个细节，上述对答案数组的修改时，没有带上权 a_i（答案要求的是最大值和而不是个数啊喂），写代码时注意一下。

代码

我觉得我写的有点乱，就只放链接了：Code。