問題
平面上の $N$ 点 $(x_i,y_i)$ について、任意の2点間にマンハッタン距離 $|x_i-x_j|+|y_i-y_j|$ を重みとする完全グラフの最小全域木の総重みを求めよ。
制約
$1 \le N \le 2 \times 10^5$
$-10^9 \le x_i, y_i \le 10^9$
完全グラフ（辺 $O(N^2)$）
時間制限: 2sec
入出力例
入力例 1
4
0 0
1 1
2 0
0 2出力例 1
6概念図: 8オクタント最近傍のみ候補
ヒント（段階的開示）
ヒント1: 方向性
完全グラフの辺は $O(N^2)$。マンハッタンMSTでは各点について8つの45度オクタントそれぞれで最近傍とだけ辺を張れば十分。候補辺は $O(N)$ 本に削減できる。
ヒント2: アプローチ
- 対称性より右側4オクタントを考え、座標反転で8方向カバー
- 各オクタント内最近傍は点をソート + BIT で $x \pm y$ の最小を管理するスイープで $O(N\log N)$
- 候補 $O(N)$ 本で通常の Kruskal
ヒント3: 誘導
代表実装: $x+y$ 降順スイープ、$x-y$ で座圧した BIT に suffix-min を持たせる。座標を $(x,y)\to(y,x),(x,-y),\dots$ と変換し計4回スイープ×反転で全8オクタント。
模範解答 (Python)
import sys
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
xs = [0]*N; ys = [0]*N
for i in range(N):
xs[i] = int(data[idx]); ys[i] = int(data[idx+1]); idx += 2
edges = []
def add_edges(px, py):
order = sorted(range(N), key=lambda i: (px[i] + py[i]), reverse=True)
avals = sorted(set(px[i] - py[i] for i in range(N)))
comp = {v: k for k, v in enumerate(avals)}
sz = len(avals)
INF = float('inf')
bit_val = [INF]*(sz+1); bit_idx = [-1]*(sz+1)
def upd(pos, val, who):
pos += 1
while pos <= sz:
if val < bit_val[pos]:
bit_val[pos] = val; bit_idx[pos] = who
pos += pos & (-pos)
def qry(pos):
pos += 1; best = INF; bi = -1
while pos > 0:
if bit_val[pos] < best:
best = bit_val[pos]; bi = bit_idx[pos]
pos -= pos & (-pos)
return bi
for i in order:
a = comp[px[i] - py[i]]
j = qry(sz - 1 - a)
if j != -1:
w = abs(px[i]-px[j]) + abs(py[i]-py[j])
edges.append((w, i, j))
upd(sz - 1 - a, px[i] + py[i], i)
X = xs[:]; Y = ys[:]
for rot in range(4):
add_edges(X, Y)
add_edges(Y, X)
X, Y = Y[:], [-v for v in X]
parent = list(range(N))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]; x = parent[x]
return x
edges.sort()
total = 0; cnt = 0
for w, u, v in edges:
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv; total += w; cnt += 1
if cnt == N - 1: break
print(total)
solve()
Step-by-Step 解説
1候補辺の削減原理
点 $p$ を中心に8オクタントに分け、各オクタント内の最近傍とだけ繋げばMSTの全辺を含む（幾何補題）。候補 $O(N)$ 本。
点 $p$ を中心に8オクタントに分け、各オクタント内の最近傍とだけ繋げばMSTの全辺を含む（幾何補題）。候補 $O(N)$ 本。
2オクタント内最近傍
1オクタントでは $x+y$（または $x-y$）の単調性を使い、点をソートしてBITで「条件を満たす点のうち $x+y$ 最小」を $O(\log N)$ で引く。
1オクタントでは $x+y$（または $x-y$）の単調性を使い、点をソートしてBITで「条件を満たす点のうち $x+y$ 最小」を $O(\log N)$ で引く。
3座標変換で8方向
1回のスイープは1オクタント分。$y=x$ 反転と90度回転で計8回（4回転×2）スイープすれば全方向網羅。
1回のスイープは1オクタント分。$y=x$ 反転と90度回転で計8回（4回転×2）スイープすれば全方向網羅。
4Kruskal
集めた $O(N)$ 本を重みソート、Union-Find でMST構築。$O(N\log N)$。
集めた $O(N)$ 本を重みソート、Union-Find でMST構築。$O(N\log N)$。
5全体計算量
スイープ $O(N\log N)$ × 定数回 + Kruskal $O(N\log N)$ = $O(N\log N)$。
スイープ $O(N\log N)$ × 定数回 + Kruskal $O(N\log N)$ = $O(N\log N)$。
計算量
候補辺生成（スイープ×定数回）: $O(N\log N)$
Kruskal: $O(N\log N)$
全体: $O(N\log N)$
空間: $O(N)$
Kruskal: $O(N\log N)$
全体: $O(N\log N)$
空間: $O(N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 全 $O(N^2)$ 辺を生成 | 削減原理未適用 | 8オクタント最近傍のみ |
| BITをprefix-minで使う | suffix-minが必要 | インデックス反転で suffix→prefix |
| オクタント網羅漏れ | 変換回数不足 | 反転+回転で全8方向確認 |
| 座圧の重複値 | set化忘れ | sorted(set(...)) |
次のステップ
- 発展問題: ユークリッド距離MST（Delaunay三角形分割 → MST）
- 類題: Chebyshev距離（45度回転でManhattanに帰着）
- 応用: 回路配線、single-linkageクラスタリング