ABC407F - Sums of Sliding Window Maximum

問題

整数列$A$が与えられます。$k=1, 2, \cdots, N$について、以下の問題を解いて下さい。

• $A$の長さ$k$の連続部分列は$N-k+1$個存在するが、それぞれについての最大値を合計したものを求めよ。

解法

問題をそのまま解くのは不可能なので、代わりに各値について寄与を考える。すなわち、$A_i$が長さ$k$の連続部分列の最大値として現れるのは何回か？を考えれば良い。

$A_i$が長さ$k$の連続部分列の最大値として現れることを考えるために、$A_i$以下の要素が、$A_i$の左右にいくつ伸びているか？を知りたい。これはとを用いることで問題なく取得することができる。以降、をかつを満たす最小値、をかつを満たす最大値として定義する。

この区間において、$i$を含んでかつ長さ$k$の連続部分列がいくつ存在するかを考えよう¹。 まず、$k \leq \text{min}(l, r)$である間は、ちょうど$k$個の連続部分列が存在する。これは左右にいくらでも伸ばせるので、$$を長さのうち何番目に置くか？という話を考えれば良い。次にである間、片端がより伸ばせず、もう片方はいくらでも伸ばせるのでのままである。最後にの場合は、両端に自由度がなくなっていくので、となる。

答え$C_k(k=1,2,\cdots,N)$に対する寄与の回数を、例えば$l=4,r=2$で考えると、となる。これは左右が等差数列、真ん中が同じ値になっていて簡単に区間演算をするのが難しいが、「増加部分の+と減少部分の-を区間加算」ができればimos法で求めることができるので、区間加算の遅延セグメントツリーを用いれば良い。

以上を実装することで、全体で$O(N\log N)$時間で解くことができる。提出(C++, 249ms)

// 区間加算にしか興味がないので、Sの演算は何でもOK
using S = long long;
using F = long long;

const S INF = 8e18;

S op(S a, S b){ return std::