Official

E - Sorting Queries Editorial by Nyaan


まず、与えられたクエリを文字通りそのまま配列で処理すると TLE してしまいます。なぜならば、各クエリの計算量は \(n\) を要素数として

  • クエリ \(1\) : \(\mathrm{O}(1)\)
  • クエリ \(2\) : \(\mathrm{O}(n)\)
  • クエリ \(3\) : \(\mathrm{O}(n \log n)\)

であるため、たとえば「クエリ \(1\)\(\frac{Q}{2}\) 回 → クエリ \(3\)\(\frac{Q}{2}\) 回」といった例で \(\mathrm{O}(Q^2 \log Q)\) 程度の計算量が掛かってしまうためです。

まず、配列をソート済みの部分とそうでない部分に分けて考えます。するとこの問題は次のように言い換えられます。

配列\(A_1\) とソート済み配列 \(A_2\) がある。以下のクエリを処理せよ。

  • クエリ \(1\) : \(A_1\) の最後尾に \(x\) を追加
  • クエリ \(2\) : \(A_2\) が空でない場合は \(A_2\) の最初の要素、空の場合は \(A_1\) の先頭の要素を出力して削除
  • クエリ \(3\) : \(A_1\) の要素をすべて \(A_2\) に移して \(A_2\) をソート

ここでクエリ \(1\)\(A_1\) を配列ではなく キュー で管理することで \(\mathrm{O}(1)\) で処理することができるので高速化できます。問題はクエリ\(3\) です。

ここで、出力クエリであるクエリ \(2\) で必要とされている情報が \(A_1, A_2\) の最初の要素だけであることに注目します。ここから \(A_2\) に保持される必要があるのは 最小 の要素だけという意味になります。

よって、 \(A_2\)優先度付きキュー によってデータを管理することで計算量を削減することができます。具体的には以下に説明するアルゴリズムを構成することで、毎回ソートする必要が無くなり高速化が可能になります。

キュー \(Q_1\) と最小値を優先的に取り出す優先度付きキュー \(Q_2\) を用意して、クエリを以下のように処理します。

  • クエリ \(1\) : \(Q_1\)\(x\) を push する。
  • クエリ \(2\) : \(Q_2\) が空かどうかによって \(2\) つの操作のいずれかを行う。
    • \(Q_2\) が空の場合、 \(Q_1\) の先頭の要素を出力して pop する。
    • \(Q_2\) が空でない場合、 \(Q_2\) の最小の要素を出力して pop する。
  • クエリ \(3\) : \(Q_1\) 内の要素をすべて \(Q_2\) に移す。

計算量解析は少し複雑です。キューの要素数を \(|Q|\) のように表すと、各クエリの \(1\) 回あたりの最悪計算量は

  • クエリ \(1\) : \(\mathrm{O}(1)\)
  • クエリ \(2\) : \(\mathrm{O}(\log |Q_2|)\)
  • クエリ \(3\) : \(\mathrm{O}(|Q_1| \log |Q_1 + Q_2|)\)

になり、上の数字だけを見るとクエリ \(3\) の計算量が悪いため先ほどの TLE するアルゴリズムと変わらないように見えます。

ところが、このアルゴリズムの全体での計算量は実は \(\mathrm{O}(Q \log Q)\) になります。なぜならば、クエリ \(3\) の計算量の \(|Q_1|\) の部分は \(Q_2\) に要素を push した回数を意味しますが、この問題で登場する要素の個数は \(Q\) 個であるため、クエリ \(3\) で追加される要素の個数は \(\mathrm{O}(Q)\) 個に抑えられます。よってクエリ \(3\) のクエリ全体での計算量は \(\mathrm{O}(Q \log Q)\) になるというわけです。

このようにクエリ全体での計算量を解析することを 償却解析 と呼びます。また、クエリ \(3\) のようなクエリはどんなに悪くとも平均が \(\mathrm{O}(\log Q)\) で抑えられますが、このようなクエリを 「 ならし計算量 ( 償却計算量 )\(\mathrm{O}(\log Q)\) である」 という風に表現します。ならし計算量は様々なアルゴリズムの計算量解析に使用されていて、代表的なものでは動的配列 (std::vector) への要素の追加 (push_back) が挙げられます。

以上よりこの問題を \(\mathrm{O}(Q \log Q)\) で解くことができました。
別解として Segment Tree 上の二分探索を用いる解法もあります。

posted:
last update: