考察
操作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.
出典