Day 011-Q3 | 平面走査アルゴリズム

問題

$N$ 本の水平線分と垂直線分が与えられる。水平線分と垂直線分の交点の数を求めよ。

水平線分 $i$ は $(x_{i1}, y_i)$ から $(x_{i2}, y_i)$（$x_{i1} < x_{i2}$）、垂直線分 $j$ は $(x_j, y_{j1})$ から $(x_j, y_{j2})$（$y_{j1} < y_{j2}$）で表される。

入力形式

H V
x_{11} x_{12} y_1
...（H行）
x_1 y_{11} y_{12}
...（V行）

制約

$1 \le H, V \le 10^5$

座標値は $-10^9 \le \text{値} \le 10^9$

同一座標の線分は存在しない（端点共有も交点に含めてよい）

入出力例

入力例 1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

全対の $O(HV)$ 探索は $10^{10}$ で不可能。平面走査（Sweep Line）と BIT（Fenwick Tree）を組み合わせると $O((H+V) \log C)$ で解ける（$C$ は座標値の範囲）。

ヒント2: アプローチ

x 座標でイベントを整列して左から右に走査する:

水平線分の「左端」→ BIT に $y$ 座標を +1 追加
垂直線分 → BIT で $[y_{j1}, y_{j2}]$ の区間和を取得（交点数）
水平線分の「右端」→ BIT から $y$ 座標を -1 削除

ヒント3: 誘導

# イベント作成
events = []
for xl, xr, y in horizontals:
    events.append((xl, 0, y, 1))   # 左端: +1
    events.append((xr, 2, y, -1)) # 右端: -1
for x, yl, yr in verticals:
    events.append((x, 1, yl, yr)) # 垂直: クエリ

events.sort()  # x でソート。同 x 内: 左端→垂直→右端

模範解答 (Python)

import sys
from sortedcontainers import SortedList
input = sys.stdin.readline

def main():
    H, V = map(int, input().split())
    horizontals = []
    for _ in range(H):
        xl, xr, y = map(int, input().split())
        horizontals.append((xl, xr, y))
    verticals = []
    for _ in range(V):
        x, yl, yr = map(int, input().split())
        verticals.append((x, yl, yr))

    # 座標圧縮
    ys = sorted(set(
        [y for _, _, y in horizontals] +
        [yl for _, yl, _ in verticals] +
        [yr for _, _, yr in verticals]
    ))
    compress = {v: i+1 for i, v in enumerate(ys)}
    M = len(ys)

    # BIT
    bit = [0] * (M + 1)

    def update(i, delta):
        while i <= M:
            bit[i] += delta
            i += i & (-i)

    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s

    def range_query(l, r):
        return query(r) - query(l - 1)

    # イベント作成
    # type: 0=水平左端, 1=垂直クエリ, 2=水平右端
    events = []
    for xl, xr, y in horizontals:
        events.append((xl, 0, compress[y], 1))
        events.append((xr, 2, compress[y], -1))
    for x, yl, yr in verticals:
        cy1, cy2 = compress[yl], compress[yr]
        events.append((x, 1, cy1, cy2))

    events.sort(key=lambda e: (e[0], e[1]))

    ans = 0
    for ev in events:
        if ev[1] == 0:  # 水平左端
            update(ev[2], 1)
        elif ev[1] == 2:  # 水平右端
            update(ev[2], -1)
        else:  # 垂直クエリ
            ans += range_query(ev[2], ev[3])

    print(ans)

main()

Step-by-Step 解説

1平面走査の発想
「x を左から右に動かす仮想的な垂直線」を考え、その垂直線と交わりうる水平線分を管理する。

2イベントの分類とソート

type 0 (左端): 水平線分を「アクティブ」に追加 → BIT の $y$ 座標を +1
type 1 (垂直): アクティブな水平線分のうち $y \in [y_1, y_2]$ の数を BIT で取得
type 2 (右端): 水平線分を削除 → BIT の $y$ 座標を -1

同じ $x$ では 0 → 1 → 2 の順（左端→クエリ→右端）でソートする。

3座標圧縮
$y$ 座標が最大 $10^9$ なので BIT のサイズに収めるため圧縮する。$y$ 値を昇順ソートして 1-indexed の整数に対応付ける。

4BIT で区間和
range_query(l, r) は query(r) - query(l-1) で $O(\log M)$ の区間和クエリ。

よくあるミス

ミス	原因	正しい書き方
同 x の順序間違い	左端→垂直→右端でないと交点をカウントできない	sort key の第2要素で 0<1<2 を保証
圧縮後の l>r	yl>yr になりうる	圧縮前に `min/max` で正規化
BIT の 0-indexed 使用	BIT は 1-indexed	インデックスに +1

次のステップ

発展: 水平・垂直以外の任意線分の交点数（シャモス・ホーイ法）
応用: 矩形領域内の点の数クエリ（2次元平面走査）

自己評価

完全理解おおむね理解要復習

Day 011-Q3 — 平面走査アルゴリズム

問題