スライド最小値
https://qiita.com/kuuso1/items/318d42cd089a49eeb332 この記事が感覚的にわかりやすかった。
概要
長さ$ N の配列の連続$ K 個のすべての区間の最小/最大を$ O(N) で求めるやつ
手順
dequeに「最小値になりうる値」を記録していく感じ。
$ a を追加する操作
dequeの右端が$ a 未満になるまで右からpopしていく。
dequeの右端に$ a を追加する
$ a を削除する操作
dequeの左端が$ a ならpopする。
dequeの左端が$ a じゃないなら何もしない。
として、
配列の先頭$ K-1 個"追加"
→ 以下を適度に繰り返す
$ K + i 個目を"追加"
最小値を記録
$ i 個目を"削除"
補足
なんか似たような状況でbitでどうのこうのする面白い方法があった気がするけど思い出せない #TODO