ABC 217 E — Sorting Queries

考察

操作3の直後に存在した要素は昇順のまま先頭側に並び、その後の操作1で加わる要素だけが末尾へ到着順に連なる。したがって、現在の列は「ソート済み部分」と「まだ一度もソートされていない追加部分」に分けて考えられる。

操作2が必要とするのは列全体ではなく先頭だけであり、ソート済み部分からは最小値、未ソート部分からは最古の要素だけを取り出せればよい。

採用する候補: 未ソート部分を FIFO queue、ソート済み部分を min-priority queue で別々に持ち、操作3で前者の全要素を後者へ移す。

操作1の到着順と操作3後の昇順を同時に保てる。

棄却する候補: 列を一つの配列で保持し、操作3のたびに配列全体をソートする。

操作1を大量に行った後で操作3を繰り返す入力では同じ要素を何度もソートし、Q が 2×10^5 の制約に収まらない。

操作1では queue へ追加し、操作2では heap が非空ならその最小値、空なら queue の先頭を出力して削除する。操作3では queue が空になるまで要素を heap へ移し、明示的な全体ソートを行わない。

典型の発動条件

列の状態分割

発動条件: 一部の操作だけが既存要素を並べ替え、その後の追加要素は並べ替え済み部分の後ろに残るとき。

操作履歴の境界で列をソート済み部分と未処理 suffix に分け、それぞれに必要な順序だけを持つデータ構造を割り当てる。

償却解析

発動条件: 一回だけ見ると重い一括移動がある一方、各要素がその移動を経験する回数を制限できるとき。

操作3で移した個数の総和を、操作1で追加された全要素数以下として数える。

問題固有の要素

「sort」は過去の全要素だけを heap 側へ確定させ、以後に append された要素の FIFO 順までは壊さない。

別の問題へ持ち帰る視点: 更新が列全体へ及ぶように見えたら、更新時点より前と後の要素で意味が変わらないかを調べ、履歴の境界を状態として残す。

正当性

heap が空でなければその最小値が必ず列の先頭であり、heap が空になって初めて queue の先頭が列の先頭になる。 操作1の到着順と操作3後の昇順を同時に保てる。各要素が queue から heap へ移るのは高々一度なので、操作3の一回の重さではなく全クエリを通した仕事量で評価できる。

実装上の注意

  • queue の先頭削除を配列の shift で実装せず、deque または読み取り index を使う。重複値は heap に個別要素としてそのまま保持する。

復習の核

  • サンプル1の操作3の直後と、その後に 0 を追加した直後を書き出し、heap を queue より先に読む理由を言葉で再確認する。

計算量と制約

時間

全Q操作でO(Q log Q)、queueの各要素は高々一度heapへ移る。

空間

O(Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq Q \leq 2 \times 10^5; 0 \leq x \leq 10^9; A will not be empty when a query 2 is given.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sorting Queries の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単調進行による償却解析

主題
  • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
追加で学ぶ技能
    なし
    既習技能
    • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 単調進行による償却解析

    補助タグ: priority queue・best-first列挙

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 単調進行による償却解析

    • 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

    先に読む単元:

    • priority queue・best-first列挙 — 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題