Ark's Blog

数学とか競プロとか参加記とか備忘録とか

ようこそ

全順序集合に対するimos法の拡張

AtCoder Beginner Contest 128のE - Roadworkで、imos法を拡張したアルゴリズムを思いついたのでメモ。

前提

  • imos法を知らない人はこちら
  • imos法は可換群に対して特定のクエリを高速に処理するアルゴリズム
  • 今回は全順序集合への拡張を考えた

定式化

「E - Roadwork」は座標圧縮などを使うと次の問題に帰着できる。

  1. 以下が与えられる:
    • 最大元  \text{INF} をもつ全順序集合  (X, \leq)
    • 自然数  M と集合  I := \{0, 1, \ldots, M-1\}
  2.  \text{INF} で埋められた長さ Mの配列 Rを用意する。
  3.  N 個の次のクエリ  (l_i, r_i, x_i) \in I \times I \times X  \text{ where } l_i \leq r_i \land x_i \lt \text{INF} を処理する:
    •  ^\forall c \in \lbrack l_i, r_i)に対して  R\lbrack c\rbrack \leftarrow \min(R \lbrack c \rbrack , x_i) の更新をする。
  4.  Q 個の次のクエリ  q_i \in I を処理する:
    • 現在の  R \lbrack q_i \rbrack の値を出力する。

愚直な解法

  • クエリを順に愚直に処理すると、全体の計算量は O(NM + Q)となる。
  • 配列を使わずに Q個のクエリを処理する場合は O(NQ)となる。

制約が「 \leq 10^5」だと間に合わないので O(\ast \log \ast)に落としたい。

imos法っぽい解法

  1. vector<X>( X上の動的配列)*1を要素にもつ大きさ Mの配列を2つ用意する。これを配列  U_\text{insert}, U_\text{remove}とする。
  2.  N個のクエリ (l_i, r_i, x_i)に対して次のように処理する:
    1.  U_\text{insert}\lbrack l_i \rbrack.\text{push}(x_i)
    2.  U_\text{remove}\lbrack r_i \rbrack.\text{push}(x_i)
  3.  X上の重複要素を許す平衡二分探索木 Tを用意する。具体的には次のメソッドがある:
    •  \text{insert}(x) O(\log n) xを挿入する。すでに xが入っている場合も重複して挿入する。
    •  \text{remove}(x) O(\log n) x1つ削除する。
    •  \text{min}():もっている要素のうち最小の値を O(1)で返す。空のときは \text{INF}を返す。
  4.  \text{for } i \leftarrow 0 \text{ to } {M-1}
    1.  \text{for } x \in U_\text{insert}\lbrack i \rbrack
      1.  T.\text{insert}(x)
    2.  \text{for } x \in U_\text{remove}\lbrack i \rbrack
      1.  T.\text{remove}(x)
    3.  R\lbrack i \rbrack \leftarrow T.\text{min}()
  5.  Q個の次のクエリ q_iに対して次のように処理する:
    1.  R\lbrack q_i \rbrackを出力する。

このようにimos法っぽいアルゴリズムでクエリを処理すると、時間計算量は

  • (2)で O(N)
  • (4)で O(M + N\log N)
  • (5)で O(Q)

となり、全体の時間計算量は O(M + Q + N\log N)となる*2

まとめ的なにか

ぶっちゃけ遅延セグ木があれば事足りるので、不要なアルゴリズムな気もする。

ただし実装は楽だし、たぶん定数倍も遅延セグ木より早いので、使える場面はあるかもしれない。


*1:挿入が O(1)でtraverseが O(n)ならqueueやvectorでも可。

*2:簡単のため X上の比較処理を O(1)と仮定している。そうでないときの計算量も簡単に求まる。