ABC 231 F — Jealous Two

考察

喧嘩しない順序付き点対は A_i≥A_j かつ B_i≤B_j。A昇順、同じAではB降順に処理すると、前側の点にA条件を吸収でき、現在B以上の頻度をsuffix queryで数えられる。

完全一致する点がc個なら群として扱う。未登録の群に対してFenwickのsuffix queryを行い、外部点との寄与 c×query と群内の順序付き寄与 c² を加えてから、その群の頻度cを登録する。

採用する候補: Aでsweepし、圧縮B上のsuffix頻度をFenwickで求める。

群をまとめてquery後に登録することで、同一群の点を誤って片方向だけ数えるのを避ける。

棄却する候補: 全ての順序付き組を二重ループで調べる。

点対がN²個ある。

典型の発動条件

二次元半順序の sweep line

発動条件: 点対に x の一方向不等式と y の逆方向不等式が同時に課されるとき。

x をソート順で満たし、処理済み点の y 頻度から現在閾値以上の個数を取得する。

座標圧縮と Fenwick tree

発動条件: 座標値は大きいが、挿入と prefix・suffix 個数問合せだけを行うとき。

B の順位へ一点加算し、全挿入数から B_i 未満の prefix 和を引く。

問題固有の要素

同じ品を二人へ渡すことも許されるため i=j を含み、同一座標が c 個ならその群内だけで c² 個の順序付き組が有効になる。

別の問題へ持ち帰る視点: dominance counting では、不等号が非厳密か、組が順序付きか、同一点と自己対を含むかをグループ単位で確認する。

正当性

A が同値の点では B の大きい順に置くことで条件を満たす向きが処理済み側に現れるが、完全に同じ点の複数個はまとめて双方向を数える必要がある。 一方の不等式をソート順へ吸収し、他方を一次元の動的な範囲和へ落とせる。

実装上の注意

  • 同一点群のサイズをcとし、登録前にsuffix queryを取り c×query+c² を加えてから頻度cをFenwickへ反映する。
  • 答えは最大N²なので64ビット整数で持ち、B_j≥B_i の等号を含める。

復習の核

  • 二変数の不等式対が出たら、一方をソートで自動的に満たし、残る一方をデータ構造の問合せにする。
  • タイブレークは適当に決めず、同じ第一座標で有効な第二座標の向きが処理済み側へ来る順を選ぶ。

計算量と制約

時間

O(N log N)、A sortとB Fenwick。

空間

O(N)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

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

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

    補助タグ: 座標・値の順序保存圧縮 Fenwick Tree・反転数・重み付き接頭辞統計

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題