ABC407 F - Sums of Sliding Window Maximum 题解

· · 题解

ABC407 F - Sums of Sliding Window Maximum

如果直接计算，即使使用单调队列也需 O(n^2)，无法通过，由于 ans_k 的值是累加起来的和，因此考虑每个 A_i 的贡献。

容易发现，记 lt[i] 表示 i 前面第一个比 A_i 大的数的位置的下一个位置，没有则为 1，rt[i] 同理。则 A_i 可以贡献 ans_1 到 ans_{rt[i]-lt[i]+1}。单调栈 O(n) 计算即可。

此时有一个细节需要注意：相同的数可能会多贡献或者漏贡献。此时只需稍加修改，计算 lt 时把 ar[sta[top]]==ar[i] 的 pop 掉，计算 rt 时不 pop掉，就能做到不重不漏。换句话说：[lt_i,i] 中有和 A_i 相同的数，[i,rt_i] 没有与 A_i 相同的数。

接下来我们考虑是怎样贡献的。 手玩几组数据可以发现，记 pos = min(i-lt[i],rt[i]-i),len = rt[i]-lt[i]+1。则

  1. 对于 i\in[1,pos], ans_i = ans_i + i \times A_i
  2. 对于 i\in[pos+1,len-pos], ans_i = ans_i + (pos+1) \times A_i
  3. 对于 i\in[len-pos+1,len], ans_i = ans_i + (len-i+1) \times A_i

对于 1,2 操作，线段树可以维护，但是对于 3 操作，线段树无法直接维护。此时有两种方法：

  1. 记 C_i = ans_i-ans_{i-1}，则只需维护 C 的区间加操作，时间复杂度 O(n \times \log n)
  2. 又记 D_i = C_i-C_{i-1}，二次差分，则只需对 D 进行单点修改，最后二次前缀和即可，时间复杂度 O(n)

这里给出个数据：\{2,4,3,5,4\}，大家可以手模一下
代码自己写