全順序集合に対するimos法の拡張
AtCoder Beginner Contest 128のE - Roadworkで、imos法を拡張したアルゴリズムを思いついたのでメモ。
前提
定式化
「E - Roadwork」は座標圧縮などを使うと次の問題に帰着できる。
- 以下が与えられる:
- 最大元
をもつ全順序集合
- 自然数
と集合
- 最大元
で埋められた長さ
の配列
を用意する。
個の次のクエリ
を処理する:
に対して
の更新をする。
個の次のクエリ
を処理する:
- 現在の
の値を出力する。
- 現在の
愚直な解法
- クエリを順に愚直に処理すると、全体の計算量は
となる。
- 配列を使わずに
個のクエリを処理する場合は
となる。
制約が「」だと間に合わないので
に落としたい。
imos法っぽい解法
- vector<X>(
上の動的配列)*1を要素にもつ大きさ
の配列を2つ用意する。これを配列
とする。
個のクエリ
に対して次のように処理する:
上の重複要素を許す平衡二分探索木
を用意する。具体的には次のメソッドがある:
:
で
を挿入する。すでに
が入っている場合も重複して挿入する。
:
で
を1つ削除する。
:もっている要素のうち最小の値を
で返す。空のときは
を返す。
個の次のクエリ
に対して次のように処理する:
を出力する。
このようにimos法っぽいアルゴリズムでクエリを処理すると、時間計算量は
- (2)で
- (4)で
- (5)で
となり、全体の時間計算量はとなる*2。
まとめ的なにか
ぶっちゃけ遅延セグ木があれば事足りるので、不要なアルゴリズムな気もする。
ただし実装は楽だし、たぶん定数倍も遅延セグ木より早いので、使える場面はあるかもしれない。