スライド最小値

Last updated：2018-04-16　03:16:30
Tweet Category:データ構造, Tag：スライド最小値

概要

列$a$に対して区間最小値を取るクエリを複数こなす際，区間の両端位置が広義単調増加のとき，
dequeを使い全体で線形時間でクエリをこなす．

全体で$O(N)$

区間は$[L, R)$といった半開区間で管理されます．

テンプレート引数に<型, 比較関数>を指定します．

// int型の列aについて区間最小値を取る
SlideMinimum<int, std::less<>> sm(a);

// int型の列aについて区間最大値を取る
SlideMinimum<int, std::greater<>> sm(a);

実際に区間をずらすための関数をいくつか用意しています．
区間をずらす際，両端位置が広義単調増加の動きをしていないとバグるので注意

// 区間の左端Lを1増やす
sm.incL();

// 区間の右端Rを1増やす
sm.incR();

// 区間の左端Lを指定位置lまでずらす
sm.slideL(l);

// 区間の右端Rを指定位置rまでずらす
sm.slideR(r);

// 区間を[l, r)へずらす
sm.slide(l, r);

今見ている区間の最小値の要素番号を取得する際はgetIndex()を使います．

// 区間[l, r)の最小値の要素番号を取得
int mi = sm.getIndex();