ABC 401-500/ABC407F - Sums of Sliding Window Maximum - 競技プログラミング用 知識集積所

---

問題

ABC407F

必要知識

B以下レベルの内容は省略

• 階差数列（未作成）
• 累積和
• priority_queue（未作成）
• set（未作成）
• 二分探索（未作成）
• 番兵法（未作成）

考え方

タイトルにsliding window法の名前があるが、思いっきりひっかけである。
なぜなら、幅を変えながらN周分全て繰り返さないといけないためO(N^2)かかってしまうためである。
これでも愚直にやったO(N^3)よりは遥かに高速ではあるのだが。

そこで、考え方をガラリと変えてみる。
例えば入力例1の場合、各区間の最大値と総和は以下のようになっている。

区間幅		区間最大値
1		5	3	4	2
2		5	4	4	-
3		5	4	-	-
4		5	-	-	-

他の数値で試してみればわかるように、最上段は元の数列そのまま、2段目以下は上と右上の最大値となっている。
これで高速化ができて間に合う……かと思いきや、これは定数倍がよくなるだけでO(n^2)であることには変わりない。

ということで、さらに改良。
この表を埋めるのではなく、直接和を求めてしまう方針を考えてみる。
つまり、

• 5は全ての段に1回ずつ足す
• 3は1段目に1回だけ足す
• 4は1段目に1回、2段目に2回、3段目に1回足す
• 2は1段目に1回だけ足す

とすることで、同じ数を何度も何度も足す作業を掛け算で処理してはどうか、と考える。

各段に何個その値が入るかは簡単に求められる。
つまり、左右それぞれ自分以上の値が何個先にいるかを見てやればいい。
（同じ値の場合は右にある方が大きいなどと決めておく）
左が3個先、右が5個先にいるなら、上の段から順に1回、2回、3回、3回、3回、2回、1回と足すことになる。
つまり、最初が1回、そこからだんだんと1回ずつ増え、3回になったところで増加は止まり、5段目を超えたところから1回ずつ減らせばいい。
これで今度こそ高速化ができて間に合う……かと思いきや、実はまだ足りない。

というのは、実はこの方法は、単調に増加するような数列が与えられた場合にむしろ悪化している。
まず、全部の段に1回ずつ足すことになるので、元々O(n^2)が何も改善しない。
さらに、左右の何個先に自分より大きい数がいるかの探索にも合計でO(n^2)がかかってしまう。

では三度、これを改良。
まず、左右の何個先に自分より大きい数がいるかの探索の方は単純に改良ができる。
単純に値が大きいところから順に調べつつ、調査済の数値の位置をset（未作成）に記録していけばよい。
最初に番兵法（未作成）の考えで-1とnを放り込んでおけば、二分探索（未作成）した前後の値を見るだけで済み、n回の探索がO(n*logn)で終わる。

全部の段に足していく方の問題は、階差数列（未作成）を使うことで解決する。
上の例では、左が3個先、右が5個先にいるなら、上の段から順に1回、2回、3回、3回、3回、2回、1回と足すことになった。
これは、階差数列（未作成）に1回、1回、1回、0回、0回、-1回、-1回、-1回足すことに他ならない。
（最後の1回は、0回加算に戻すため）
このときに1や-1が多く並ぶデータは、他の数が深くまで続くことを阻害するデータである。
従って、n回分のデータ全部でO(n*logn)で終わる。（本当か？……自信なし）

まあ、これで不安ならば階差数列（未作成）の階差数列（未作成）を取って1回、0回、0回、-1回、0回、-1回、0回、0回、1回足せばよい。
この場合に足す位置は、0スタートで数えれば、0番目と8番目に1回足して、3番目と5番目に-1回足している。
このことから、左右の何個先に自分より大きい数がいるかから値を足すべき場所がすぐにわかる。

以上の考えを全部コードにすればよい。

解答例

解答例

注意点

階差数列（未作成）の処理がはみ出さないように注意。

末端まで足す場合、それをリセットする「-1回加える」が普通のvector（未作成）から1つはみ出る。
それを2重にやると、あわせて2個はみ出る。
if分岐で処理をスキップするか、数列のサイズを適切に取ってやること。

別解