ABC407 F - Sums of Sliding Window Maximum

如果直接計(jì)算，即使使用單調(diào)隊(duì)列也需 \(O(n^2)\)，無法通過，由于 \(ans_k\) 的值是累加起來的和，因此考慮每個 \(A_i\) 的貢獻(xiàn)。

容易發(fā)現(xiàn)，記 \(lt[i]\) 表示 \(i\) 前面第一個比 \(A_i\) 大的數(shù)的位置的下一個位置，沒有則為 \(1\)，\(rt[i]\) 同理。則 \(A_i\) 可以貢獻(xiàn) \(ans_1\) 到 \(ans_{rt[i]-lt[i]+1}\)。單調(diào)棧 \(O(n)\) 計(jì)算即可。

此時有一個細(xì)節(jié)需要注意：相同的數(shù)可能會多貢獻(xiàn)或者漏貢獻(xiàn)。此時只需稍加修改，計(jì)算 \(lt\) 時把 \(ar[sta[top]]==ar[i]\) 的 \(pop\) 掉，計(jì)算 \(rt\) 時不 \(pop\)掉，就能做到不重不漏。換句話說：\([lt_i,i]\) 中有和 \(A_i\) 相同的數(shù)，\([i,rt_i]\) 沒有與 \(A_i\) 相同的數(shù)。

接下來我們考慮是怎樣貢獻(xiàn)的。
手玩幾組數(shù)據(jù)可以發(fā)現(xiàn)，記 \(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\) 操作，線段樹可以維護(hù)，但是對于 \(3\) 操作，線段樹無法直接維護(hù)。此時有兩種方法：

1. 記 \(C_i = ans_i-ans_{i-1}\)，則只需維護(hù) \(C\) 的區(qū)間加操作，時間復(fù)雜度 \(O(n \times \log n)\)
2. 又記 \(D_i = C_i-C_{i-1}\)，二次差分，則只需對 \(D\) 進(jìn)行單點(diǎn)修改，最后二次前綴和即可，時間復(fù)雜度 \(O(n)\)

這里給出個數(shù)據(jù)：\(\{2,4,3,5,4\}\)，大家可以手模一下
代碼自己寫