ABC 396 F — Rotated Inversions

考察

kを1増やすと全値は通常+1され、旧値M-1の要素だけ0へwrapする。大小関係が変わるpairは、このwrap groupとそれ以外のpairだけである。

初期k=0のinversionを一度求めれば、各値groupの位置listからwrap時に失う/得るinversion数を線形総量で計算できる。

採用する候補: 初期inversionをFenwick treeで求め、値M-cのposition groupごとの差分でkをsweepする

棄却する候補: 各kについてB列を作り直してinversionをFenwickで数える

O(MN log M)でN,M≤2×10^5には間に合わない。

Aの初期inversionをFenwickで計算しans[0]とする。c=1..M-1でvalue=M-cのsorted positionsを取り、wrap前寄与とwrap後寄与の差を現在値へ加えてans[c]を出す。

典型の発動条件

cyclic shiftの差分更新

発動条件: 全値をmod Mで一様shiftし、順序統計を全shiftで求めるとき。

境界を跨ぐ一value groupだけのpair関係を更新する。

position listによるcross pair counting

発動条件: 特定groupと補集合の前後pair数を数えたいとき。

各positionの左/右要素数から同group分を除く。

問題固有の要素

mod rotationは全要素を動かすように見えて、相対順序が変わるのはそのstepで0へ戻る値groupだけである。

別の問題へ持ち帰る視点: cyclic order上の一様shiftでは、cutを跨ぐbucketの寄与だけを差分する。

正当性

wrap前はgroup値が最大側なので、その要素が左にあり他groupが右のpairはinversion、wrap後は最小側なので他groupが左・groupが右のpairがinversionになる。 sorted position y_rから左右の非group個数を数えれば、差分をgroup全体で重複なく足せる。 各indexはちょうど一回wrap groupとして処理され、group内positionから前後の他group要素数をO(group size)で合計でき、全体O(N log M+M)になる。

実装上の注意

  • 同値pairはinversionにならないのでgroup内部を除外する。空groupのstepもanswerをそのまま引き継ぎ、値とcの対応M-cを確認する。

復習の核

  • N,M≤8で全kのBを直接作り、duplicate値、空value group、全同値、M=1を比較する。

計算量と制約

時間

O(N log M+M)、初期反転Fenwickと各値group wrap差分総走査N。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le N,M \le 2\times 10^5; 0 \le A_i < M; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

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

    主タグ: 寄与の数え上げと順序交換

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

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

    学習の位置

    体系上の位置: 局所寄与へ分解して集計順を交換する

    • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

    先に読む単元:

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

    • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題