ABC 233 Ex — Manhattan Christmas Tree

考察

座標を u=x+y、v=x−y へ 45 度回転すると、元のマンハッタン距離は max(|Δu|,|Δv|) というチェビシェフ距離になる。

距離 r 以下の木は回転後の軸平行長方形 [u−r,u+r]×[v−r,v+r] 内の点であり、その個数が K 以上かは r に対して単調である。

棄却する候補: 各クエリについて全 N 本の木とのマンハッタン距離を計算し、K 番目を選ぶ。

N と Q がともに 10 万で、全点対距離を調べられない。

採用する候補: 各クエリの答えを並列二分探索し、同じ反復の全長方形内点数を x sweep と y 座標 Fenwick tree でオフライン計算する。

距離判定を軸平行長方形数え上げへ変換し、全クエリを各反復でまとめて点・イベントの一走査にできる。

長方形内点数は x≤u+r の prefix 個数から x<u−r の prefix 個数を引き、各 prefix を y 区間和で求められる。

K 番目距離を単調な個数判定へ変え、回転座標の矩形問合せを二つの x-prefix イベントへ分解して、parallel binary search と BIT sweep を重ねる。

典型の発動条件

マンハッタン距離の 45 度回転

発動条件: 二次元の |Δx|+|Δy| 距離球を範囲数え上げへ変換したいとき。

x+y と x−y を座標にし、距離 r の菱形を軸平行正方形へ写す。

並列二分探索とオフライン矩形計数

発動条件: 多数のクエリがそれぞれ単調な閾値を持ち、一つの候補値集合を一括 sweep で判定できるとき。

各クエリの mid 長方形を左右二イベントにし、x 順に点を追加しながら BIT の y 区間和を取る。

問題固有の要素

K 番目の距離そのものを選択する代わりに、「半径 r 内の木が K 本以上」という累積個数へ置くと二分探索可能になる。

別の問題へ持ち帰る視点: 順序統計量の幾何クエリは、閾値内の要素数を返す counting oracle を設計して答えの二分探索へつなげる。

正当性

座標変換は距離r以内の条件を二座標の閉区間条件に写す。二つのprefixイベントの差はその矩形内の点だけを数えるため、判定は元の距離判定と一致する。点数がK以上となる最初の距離を各二分探索が求める。

実装上の注意

  • v=x−y は負になり得るので全点と問合せ端点を圧縮し、長方形の上下端を非厳密に含める。
  • 左境界イベントは x<u−r、右境界イベントは x≤u+r となるよう、同じ x の点と問合せイベントの処理順を揃える。

復習の核

  • K 番目の幾何距離を見たら、半径内個数の単調性と、その距離球を数えやすい図形へ変える座標変換を探す。
  • オフライン矩形数え上げでは、開区間・閉区間をイベントの座標と同値時の順序まで含めて検証する。

計算量と制約

時間

O(log C·(N+Q)log(N+Q))、C距離域、parallel binary search各roundで一BIT sweep。

空間

O(N+Q)。

制約との対応

公式制約の確認範囲: Time limit: 7 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 10^5; 0\leq x_i\leq 10^5; 0\leq y_i\leq 10^5; (x_i,y_i) \neq (x_j,y_j) if i\neq j.; 1\leq Q \leq 10^5; 0\leq a_i\leq 10^5; 0\leq b_i\leq 10^5; 1\leq K_i\leq N; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Manhattan Christmas Tree の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: parallel binary search・多数境界の判定共有

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

    主タグ: parallel binary search・多数境界の判定共有

    補助タグ: event・値順のオフライン走査 Fenwick Tree・反転数・重み付き接頭辞統計 幾何の基本判定・配置・座標変換 累積和・差分配列

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

    学習の位置

    体系上の位置: parallel binary search・多数境界の判定共有

    • 各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題