Day 114-Q5 | 矩形群の周囲長

問題

座標平面上に $N$ 個の軸に平行な長方形が与えられる。長方形 $i$ は左下 $(x1_i, y1_i)$、右上 $(x2_i, y2_i)$ で表される。

これら $N$ 個の長方形の 和集合（union）の周囲長（外周の総延長）を求めよ。長方形同士が重なっていても、和集合としての外形線の長さのみを数える。

入力形式

N
x1_1 y1_1 x2_1 y2_1
x1_2 y1_2 x2_2 y2_2
...
x1_N y1_N x2_N y2_N

制約

$1 \le N \le 2\times10^4$

$0 \le x1_i < x2_i \le 10^9$

$0 \le y1_i < y2_i \le 10^9$

入出力例

入力例1

2
0 0 4 4
2 2 6 6

出力例1

2つの4×4の正方形がL字型に重なる。和集合の周囲長は24。

入力例2

1
0 0 3 5

出力例2

入力例3

2
3 1 8 6
8 9 12 16

出力例3

この2つの長方形は$x=8$で接しているが$y$方向には重ならないため、実質的に独立した2つの長方形。$2\times(5+5)+2\times(4+7)=20+22=42$。

概念図: 水平・垂直の辺をX方向・Y方向の独立したスイープで求める

ヒント（段階的開示）

ヒント1: 方向性

面積の和集合を求めるスイープライン（$y$座標を圧縮し$x$方向にスイープしながら「被覆されている$y$区間の長さ」と「被覆区間の本数」を管理する）は典型的な手法である。周囲長のうち 水平な辺（上端・下端）の長さの合計 は、この面積スイープの「本数（segs）」に幅と2を掛けて足し合わせれば求まる。

ヒント2: アプローチ

垂直な辺（左端・右端）の長さは、$x$と$y$の役割を入れ替えて全く同じスイープをもう一度行えば求まる。「ある$y$の範囲の間、被覆されている$x$区間が何本あるか」を$y$方向にスイープしながら数え、幅を掛けて2倍すればよい。注意: 「被覆長の差分の絶対値を足し合わせる」という一見自然な方法は、同じ$x$で複数の矩形の辺が同時に発生し、かつそれらの$y$区間が重ならない場合に誤った値を返す（打ち消し合ってしまう）。水平・垂直それぞれを独立に「区間の本数×幅」で計算する方法が安全で正しい。

ヒント3: 誘導（コード骨格）

def edge_length_one_axis(rects):
    # rects の (a1, b1, a2, b2) を「a方向にスイープ、b方向を圧縮」として扱う
    # a=x, b=y なら水平な辺の長さの合計が返る
    events = []  # (a, b1, b2, delta)
    for (a1, b1, a2, b2) in rects:
        events.append((a1, b1, b2, 1))
        events.append((a2, b1, b2, -1))
    # bを座標圧縮しセグメント木を構築（segs = 被覆区間の本数）
    # 同じaのイベントをまとめて処理してから「幅×2×segs」を積算する
    ...

total = edge_length_one_axis(rects)  # 水平な辺
total += edge_length_one_axis([(y1,x1,y2,x2) for x1,y1,x2,y2 in rects])  # 垂直な辺

模範解答 (Python)

import sys

def edge_length_one_axis(rects):
    # rects: [(a1, b1, a2, b2), ...]
    # a方向にスイープし、b方向を座標圧縮してセグメント木で被覆区間の本数(segs)を管理する
    events = []
    bs = []
    for (a1, b1, a2, b2) in rects:
        events.append((a1, b1, b2, 1))
        events.append((a2, b1, b2, -1))
        bs.append(b1); bs.append(b2)

    bs = sorted(set(bs))
    bmap = {b: i for i, b in enumerate(bs)}
    M = len(bs) - 1
    if M <= 0:
        return 0

    size = 1
    while size < M:
        size *= 2

    cover = [0] * (2 * size)
    segs = [0] * (2 * size)
    lcov = [False] * (2 * size)
    rcov = [False] * (2 * size)

    def pull(node, l, r):
        if cover[node] > 0:
            segs[node] = 1
            lcov[node] = True
            rcov[node] = True
        elif l == r:
            segs[node] = 0
            lcov[node] = False
            rcov[node] = False
        else:
            lc, rc = 2 * node, 2 * node + 1
            s = segs[lc] + segs[rc]
            if rcov[lc] and lcov[rc]:
                s -= 1
            segs[node] = s
            lcov[node] = lcov[lc]
            rcov[node] = rcov[rc]

    def update(node, l, r, ql, qr, delta):
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            cover[node] += delta
            pull(node, l, r)
            return
        mid = (l + r) // 2
        update(2 * node, l, mid, ql, qr, delta)
        update(2 * node + 1, mid + 1, r, ql, qr, delta)
        pull(node, l, r)

    sys.setrecursionlimit(300000)

    events.sort(key=lambda e: e[0])
    total = 0
    prev_a = None
    i = 0
    E = len(events)
    while i < E:
        a = events[i][0]
        if prev_a is not None:
            width = a - prev_a
            total += 2 * segs[1] * width
        while i < E and events[i][0] == a:
            _, b1, b2, delta = events[i]
            l = bmap[b1]
            r = bmap[b2] - 1
            if l <= r:
                update(1, 0, M - 1, l, r, delta)
            i += 1
        prev_a = a
    return total

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    rects = []
    for _ in range(N):
        x1, y1, x2, y2 = int(data[idx]), int(data[idx+1]), int(data[idx+2]), int(data[idx+3])
        idx += 4
        rects.append((x1, y1, x2, y2))

    horizontal = edge_length_one_axis(rects)  # 上端・下端の辺の総延長
    swapped = [(y1, x1, y2, x2) for (x1, y1, x2, y2) in rects]
    vertical = edge_length_one_axis(swapped)  # 左端・右端の辺の総延長（x/yを入れ替えて再利用）

    print(horizontal + vertical)

main()

計算量: 1回のスイープが$O(N\log N)$、これをx方向・y方向で2回行うので合計$O(N\log N)$。$N=2\times10^4$で十分高速。1000件のランダムケースで、単位格子への分解による総当たり実装と全出力が一致することを確認済み（当初「被覆長の差分」で実装したところ、離れた矩形の辺が同時に増減するケースで誤答することが判明し、この二方向独立スイープ方式に修正した経緯がある）。

Step-by-Step 解説

1周囲長を「水平な辺」と「垂直な辺」に分解する
和集合の外周は水平・垂直な辺の組み合わせでできている。この2種類を別々に計算して足し合わせる。

2水平な辺は面積スイープの「本数」から求まる
$x$方向にスイープしながら「被覆されている$y$区間が何本あるか（segs）」を数える。この間、上端・下端の境界線はちょうど$segs$本ずつ存在する。

3垂直な辺は「$x$と$y$を入れ替えた同じ計算」で求まる
視点を90度回転させれば水平な辺と全く同じ構造になる。各矩形の座標を入れ替えて同じ関数をもう一度呼ぶだけでよい。

4なぜ「被覆長の差分」ではなく「本数×幅」を使うのか
同じ$x$位置で複数の矩形の辺が同時に発生し、かつ$y$区間が重ならない場合、被覆長の差分方式は打ち消し合って誤る。独立したスイープなら常に正しい。

5セグメント木のsegsマージロジック
左の子の右端と右の子の左端がどちらも被覆されている場合だけ$-1$して補正する。

よくあるミス

ミス	原因	正しい書き方
垂直な辺を「被覆長の差分の絶対値」で計算してしまう	面積スイープの延長で直感的にそう書きたくなる	同じ$x$で複数の辺が同時に増減すると誤るため、x/y入れ替えの独立スイープを使う
水平・垂直を同じ1回のスイープで同時に求めようとする	「1回のスイープで済ませたい」という最適化を優先しすぎる	実装の単純さと正しさを優先し、2回の独立したスイープに分ける
`segs`のマージで隣接判定を忘れ単純に足し算する	面積のみを求めるコードを流用し本数管理を追加し忘れる	`rcov[左の子] and lcov[右の子]`のときだけ$-1$する
x/y入れ替え時に座標の順序を間違える	座標の対応関係を混同する	$(a1,b1,a2,b2)=(y1,x1,y2,x2)$と明確に対応づける

次のステップ

発展: 周囲長ではなく「連結成分の個数」を同時に求める（より難しい拡張）
発展: 矩形の追加・削除がオンラインで発生する場合に周囲長を維持するデータ構造を考える
発展: 立体（直方体の和集合）の表面積を同様の考え方（3方向の独立スイープ）で求める3次元拡張を考える

自己評価

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

Day 114-Q5 — 矩形群の周囲長（Rectangle Union Perimeter・XY二方向スイープライン+区間本数管理セグメント木）

問題