ABC 283 F — Permutation Distance

考察

(i,P_i)を平面上のpointと見ると、D_iは他pointへのManhattan distance最小値で、絶対値はindex左右×value上下の4quadrantに分けられる。

各quadrantでは式が±i±P_iと、条件付きの過去/未来pointのmaxまたはminへ分離する。

採用する候補: indexを左右からsweepし、Pをkeyとするsegment treeでP_j±jのrange max/minをqueryして4quadrantの候補を更新する。

棄却する候補: 各i,jのManhattan distanceを計算して最小を取る。

N≤2×10^5に対してN² pairは多すぎる。

左→右sweepでvalue range [1,P_i)と(P_i,N]から対応するP_j+j/P_j-j extremumをqueryしD_iを更新後、P_i位置へ値を登録する。右→左でも対称な2caseを処理し、4候補のminを出力する。

典型の発動条件

Manhattan distanceのquadrant分解

発動条件: 点集合で|x-x'|+|y-y'|のnearest/farthestを条件付きに処理するとき。

符号4通りへ絶対値を外し、linear formのextremum queryにする。

sweep line+value segment tree

発動条件: 片方の座標の大小を走査順で固定し、もう片方の範囲条件付きextremumが必要なとき。

index順にpointを追加し、P区間のmax/minを取得する。

問題固有の要素

Pがpermutationなのでvalueをそのまま1…Nのsegment tree indexにでき、同値処理や座標圧縮が不要である。

別の問題へ持ち帰る視点: 一方座標がpermutationなら、2D dominance queryの残り軸を直接dense indexとして使う。

正当性

j<i,P_j<P_iではdistance=P_i+i-(P_j+j)なので、P_j<P_i上のP_j+j最大値だけが必要である。 他の3caseもP_j-jのmax/minや反対向きsweepへ変わるだけで、座標反転・値反転を使えば同じhelperを再利用できる。 全pair比較を、各pointあたり定数回のvalue range queryへ変えられる。

実装上の注意

  • j≠iを保証するためqueryしてから現在pointをupdateし、空rangeはINF/−INFとして候補に使わない。
  • 4caseの符号を個別に書く場合はA_i=P_i+i,B_i=P_i-iのどちらをmax/minするか照合する。

復習の核

  • 1つのiについて他pointを4quadrantに分け、各distance式からqueryすべきlinear formとmax/minを手で導く。

計算量と制約

時間

O(N log N)、四象限sweepと値域extremum。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times10^5; 1 \leq P _ i \leq N\ (1\leq i\leq N); i\neq j\implies P _ i\neq P _ j; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: event順にactive集合を更新する

主題
追加で学ぶ技能
    なし
    既習技能
    • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
    • 幾何の基本判定と座標変換: 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。

    主タグ: event・値順のオフライン走査

    補助タグ: 幾何の基本判定・配置・座標変換 区間monoid要約

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

    学習の位置

    体系上の位置: event順にactive集合を更新する

    • 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

    先に読む単元:

    • 幾何の基本判定と座標変換 — 座標と外積・距離式で向きや交差を代数判定し、凸幾何へ進む前提を作る。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 更新を単に逆順へ読む処理、答えの局所寄与だけを集計する順序交換、sort-uniqueしたkeyの添字化、および固定方向の単純scan。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題