ABC 392 F — Insert

考察

挿入するたびに後ろの要素を動かす代わりに、最終的な列の枠を先に用意し、後から挿入した値から位置を確定する。後続の挿入は既存要素の相対順を変えないので、未確定の枠だけを数えれば、挿入時の順位をそのまま使える。

配列へ前から直接挿入すると、1回で最大 O(N)O(N) 個の要素をずらす。毎回先頭へ挿入する場合は全体で Θ(N2)\Theta(N^2) となり、N≤5×105N\leq 5\times 10^5 では間に合わない。ここで、値 ii を入れた瞬間の位置と、全挿入後の位置を区別する。前者は PiP_i として分かっているが、後者は後続の挿入でずれる。

最終列から値 i+1,…,Ni+1,\ldots,N を取り除くと、値 1,…,i1,\ldots,i の相対順は ii 回目の挿入直後と一致する。従って、大きい値を既に最終位置へ置いた時点では、残る空き枠が値 1,…,i1,\ldots,i の場所に対応し、値 ii の最終位置は左から PiP_i 番目の空き枠になる。

公式入力例1の P=(1,1,2,1)P=(1,1,2,1) では、前向きの列は次のように変わる。

(1) ⟶ (2,1) ⟶ (2,3,1) ⟶ (4,2,3,1)(1)\ \longrightarrow\ (2,1)\ \longrightarrow\ (2,3,1)\ \longrightarrow\ (4,2,3,1)

逆向きでは、枠の番号を最終列の左から 1,2,3,41,2,3,4 として、次の順に埋める。「空き枠の順位」と「最終列の位置」は異なることに注意する。

置く値 ii置く前の空き枠の番号空き枠の順位 PiP_i確定する最終位置
41, 2, 3, 411
32, 3, 423
22, 412
1414

例えば値3を置くとき、枠1の値4を数えず、残る枠2・3・4のうち2番目を選ぶ。これが前向きの列 (2,3,1)(2,3,1) における値3の順位2に対応する。

空き枠を1、埋まった枠を0とする長さ NN の列 BB を Fenwick Tree で管理する。全て1で初期化し、i=N,N−1,…,1i=N,N-1,\ldots,1 の順に、接頭辞和が PiP_i 以上になる最小位置 pp を探す。答えの pp 番目に値 ii を書き、BpB_p を1から0へ更新する。最後に答えを左から出力する。

この順位探索は、接頭辞和を取得しながら外側で位置を二分探索すると1回 O(log⁡2N)O(\log^2 N) かかる。Fenwick Tree 内の区間和を直接使えば、1回 O(log⁡N)O(\log N) にできる。1始まりの内部配列を tree とし、探索中は「既に読み飛ばした接頭辞の末尾」pp と「その右側で探す残り順位」kk を保つ。初期値は p=0,k=Pip=0,k=P_i である。

NN 以下の最大の2の冪を dd として、大きい桁から dd を半分ずつにする。q=p+d≤Nq=p+d\leq N なら tree[q] を調べる。この探索順では pp が 2d2d の倍数なので、tree[q] はちょうど区間 p+1,…,qp+1,\ldots,q の空き枠数を表す。その個数が kk 未満なら、探す枠は区間の右にある。区間全体を飛ばして p=qp=q とし、その個数を kk から引く。個数が kk 以上なら、探す枠は区間内にあるので飛ばさず、次の小さい桁を調べる。範囲外の qq も飛ばさない。

全桁を調べると、pp は接頭辞和が PiP_i 未満である最後の位置になり、答えは p+1p+1 である。各桁で区間和を一つ読むだけなので、探索全体は O(log⁡N)O(\log N) になる。

典型の発動条件

操作の逆転

逐次挿入で位置が広くずれても、既存要素同士の相対順が保存されるなら、後から挿入した要素を除いて過去の列を復元できる。最終枠を固定し、逆順に未確定枠の順位を使う方法が候補になる。

動的な非負の頻度列で、累積個数が指定順位に達する最初の位置を求めたいときに使う。非負だから接頭辞和が単調になり、区間個数と残り順位の比較で区間全体を読み飛ばせる。負の頻度を許すと、この探索の前提が崩れる。

問題固有の要素

値 ii がそのまま挿入時刻を表すため、値の降順に最終位置を決められる。PiP_i は固定された位置ではなく、その時点で残る空き枠の順位として読み替える。この対応によって、前向きの位置ずれを明示的に処理する必要がなくなる。

正当性

後続の挿入は既存要素の相対順を変えない。従って、最終列から値 i+1,…,Ni+1,\ldots,N を取り除いた残りの列は、ii 回目直後の列と一致する。

逆順で値 ii を置く直前に、値 i+1,…,Ni+1,\ldots,N は正しい最終位置にあり、空き枠を左から見た順序は ii 回目直後の列の各要素に対応する、という不変条件を保つ。初めの i=Ni=N では全枠が空いており、この対応が成り立つ。ii 回目直後の列では値 ii は PiP_i 番目なので、不変条件より PiP_i 番目の空き枠がその正しい最終位置である。

その枠を埋めて空き枠から除くと、値 ii を取り除いた順序、すなわち i−1i-1 回目直後の列との対応が残る。よって不変条件は次にも保たれる。空き枠はちょうど ii 個あり、1≤Pi≤i1\leq P_i\leq i なので選ぶ枠も必ず存在する。全ての値を置き終えると、全枠が正しい最終列になる。

実装上の注意

  • PiP_i は1始まりの順位である。上の内部探索が得る pp は答えの一つ手前なので、選ぶ位置は p+1p+1。答え配列が0始まりなら変換する。
  • 区間を飛ばせる条件は空き枠数が残り順位「未満」であること。等しいときに飛ばすと、求める枠も通り過ぎる。
  • 1始まりの tree[q] は末尾から q & -q 個の和を持つ。全1の列なら tree[q] = q & -q として O(N)O(N) で構築できる。選んだ位置には通常の点加算で −1-1 を反映する。

復習の核

  • 挿入が位置をずらしても相対順を保つなら、後から挿入した値を除いた列と、過去の列を対応させる。
  • 「空きが足りる」だけでは順位を使う証明にならない。未確定枠の順序が何と一致するかを言葉にする。
  • Fenwick 内の順位探索では、飛ばした接頭辞と残り順位を保つ。接頭辞和の外側二分探索とは計算量が異なる。

計算量と制約

時間

全1の Fenwick Tree の構築は O(N)O(N)。各値について順位探索と点更新をそれぞれ O(log⁡(N+1))O(\log(N+1)) で行い、出力に O(N)O(N) かかるので、全体で O(Nlog⁡(N+1))O(N\log(N+1))。通常は O(Nlog⁡N)O(N\log N) と表すが、ここでは N=1N=1 の定数時間も含めた。

空間

入力の PP、答え配列、Fenwick Tree をそれぞれ長さ NN で保持するので O(N)O(N)。

制約との対応

公式制約は 1≤N≤5×1051\leq N\leq 5\times 10^5、1≤Pi≤i1\leq P_i\leq i。空き枠の頻度は常に0または1であり、順位探索に必要な接頭辞和の単調性が保たれる。Pi=1P_i=1 なら最左の空き枠、Pi=iP_i=i なら最右の空き枠を選び、N=1N=1 も同じ手順で処理できる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 時間を逆向きにして未来依存を消す

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 逆向きのオフライン処理

    補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計

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

    学習の位置

    体系上の位置: 時間を逆向きにして未来依存を消す

    • 時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。

    先に読む単元:

    この解説で扱わないこと:

    • 値順eventを前から処理するsweep、時刻を反転せずに行う通常のonline更新、および答えの局所寄与だけを集計する順序交換。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題