スライド最小値
長さ N の配列から長さ M (<= N) の区間最小値を求める.
もちろん区間最大値なども可能.
ナイーブにやると O(N^2) か O(NlogN)
std::deque を用いることで O(N)
deque を常に値が単調減少かつ追加時刻が単調減少であるようにする.
つまり前に行くほど値が古く・小さい
前から配列を舐めつつ deque に末尾に追加していく.
既に入っている値のうち,長さ M の範囲外のものは削る(前から順にみて消す).
既に入っている値のうち,新しく入れる値よりも大きいようなものは無駄なので削る(後ろから順に消す).
すると条件を保ったまま更新出来る,かつ一番前がその区間の最小値になっている.
code:c++
std::deque<int> qu;
for(int i = 0; i < n; i++) {
while(!qu.empty() and i - qu.front() >= M) qu.pop_front();
while(!qu.empty() and vecqu.back() >= val) qu.pop_back(); qu.push_back(i);
}