Day 126-Q5 | Klee's Measure Problem（矩形群の合併面積）

問題

2次元平面上に $N$ 個の軸平行矩形が与えられる。$i$番目の矩形は、左下座標 $(x_{1,i}, y_{1,i})$ と右上座標 $(x_{2,i}, y_{2,i})$ で表される。

これら $N$ 個の矩形の和集合の面積（重なっている部分は1回だけ数える）を求めよ。

入力形式

N
x1_1 y1_1 x2_1 y2_1
...
x1_N y1_N x2_N y2_N

制約

$1 \le N \le 200000$

$0 \le x_{1,i} < x_{2,i} \le 10^9$

$0 \le y_{1,i} < y_{2,i} \le 10^9$

座標はすべて整数

入出力例

入力例1

2
0 0 4 4
2 2 6 6

出力例1

16+16-重なり4=28

入力例2

出力例2

3矩形は接するだけで重ならないため単純和4+4+4=12

概念図

ヒント（段階的開示）

ヒント1（方向性）

これは「区間の合併長」を1次元で求める問題（Klee's Measure Problemの1次元版）を2次元に拡張したものと考えられる。矩形を$x$座標でイベント（開始・終了）として捉え、$x$方向にスイープしながら、その瞬間の「$y$方向の被覆区間の合併長」を管理できれば、両者を掛け合わせて積分していくことで面積が求まる。

ヒント2（アプローチ）

すべての矩形を「$x=x_1$で$[y_1,y_2]$を+1」「$x=x_2$で$[y_1,y_2]$を-1」という2つのイベントに分解し、$x$座標でソートする。イベントを順に処理しながら、隣接するイベントの$x$座標の差$\Delta x$と、その区間で「現在アクティブな$y$区間の合併長」$L$の積$\Delta x\times L$を足し合わせる。$L$を高速に管理するために、$y$座標を座標圧縮した上で区間加算+全体被覆長取得ができる特殊なセグメント木を使う。

ヒント3（誘導）

def update(node, l, r, ql, qr, val):
    if qr <= l or r <= ql:
        return
    if ql <= l and r <= qr:
        cover_cnt[node] += val
    else:
        mid = (l + r) // 2
        update(2*node, l, mid, ql, qr, val)
        update(2*node+1, mid, r, ql, qr, val)
    if cover_cnt[node] > 0:
        covered_len[node] = ys[r] - ys[l]
    elif r - l == 1:
        covered_len[node] = 0
    else:
        covered_len[node] = covered_len[2*node] + covered_len[2*node+1]

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1

    rects = []
    ys_set = set()
    for _ in range(n):
        x1 = int(data[idx]); idx += 1
        y1 = int(data[idx]); idx += 1
        x2 = int(data[idx]); idx += 1
        y2 = int(data[idx]); idx += 1
        rects.append((x1, y1, x2, y2))
        ys_set.add(y1)
        ys_set.add(y2)

    ys = sorted(ys_set)
    y_index = {y: i for i, y in enumerate(ys)}
    m = len(ys) - 1

    if m <= 0:
        print(0)
        return

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

    cover_cnt = [0] * (2 * size)
    covered_len = [0] * (2 * size)
    leaf_width = [0] * size
    for i in range(m):
        leaf_width[i] = ys[i + 1] - ys[i]

    prefix_width = [0] * (size + 1)
    for i in range(size):
        prefix_width[i + 1] = prefix_width[i] + (leaf_width[i] if i < m else 0)

    def seg_width(l, r):
        return prefix_width[r] - prefix_width[l]

    def update(node, node_l, node_r, ql, qr, val):
        if qr <= node_l or node_r <= ql:
            return
        if ql <= node_l and node_r <= qr:
            cover_cnt[node] += val
        else:
            mid = (node_l + node_r) // 2
            update(2 * node, node_l, mid, ql, qr, val)
            update(2 * node + 1, mid, node_r, ql, qr, val)
        if cover_cnt[node] > 0:
            covered_len[node] = seg_width(node_l, node_r)
        elif node_r - node_l == 1:
            covered_len[node] = 0
        else:
            covered_len[node] = covered_len[2 * node] + covered_len[2 * node + 1]

    events = []
    for (x1, y1, x2, y2) in rects:
        yl = y_index[y1]
        yr = y_index[y2]
        events.append((x1, yl, yr, 1))
        events.append((x2, yl, yr, -1))
    events.sort(key=lambda e: e[0])

    sys.setrecursionlimit(10000)

    area = 0
    prev_x = events[0][0]
    i = 0
    ne = len(events)
    while i < ne:
        cur_x = events[i][0]
        dx = cur_x - prev_x
        if dx > 0:
            area += dx * covered_len[1]
        while i < ne and events[i][0] == cur_x:
            _, yl, yr, val = events[i]
            update(1, 0, size, yl, yr, val)
            i += 1
        prev_x = cur_x

    print(area)


solve()

Step-by-Step 解説

11次元合併長からの拡張
「N個の区間の和集合の長さ」を求める古典問題は、区間の開始・終了をイベントとしてソートし、アクティブな区間数（重複度）が1以上の部分の長さを積算すれば解ける。矩形和集合の面積は、これを「x方向にスイープしながら各瞬間のy方向合併長を求める」形に一般化したもの。

2イベントの構成
各矩形について$x=x_1$で「$y$区間$[y_1,y_2]$のアクティブ度+1」、$x=x_2$で「同区間-1」という2つのイベントを作り、$x$座標でソートして順に処理する。

3Klee's Measure Problem用セグメント木
y座標を座標圧縮し、各リーフは隣接座標間の幅を表す。各ノードは区間加算カウントcover_cntと実カバー長covered_lenを持つ。cover_cnt>0ならそのノード区間は全てカバーされているとみなす（lazy propagationなしで区間加算と全体カバー長取得が両立する特殊な性質）。

4面積の積算
隣接イベントの$x$座標の差$\Delta x$と、直前までに確定した$y$方向合併長（ルートのcovered_len）の積を足し合わせる。同じx座標のイベントは全てまとめて処理してから次の$\Delta x$を計算する。

5計算量
イベント数$O(N)$、各更新$O(\log N)$なので全体で$O(N\log N)$。

よくあるミス

ミス	原因	正しい書き方
同じx座標の複数イベントを1つずつ処理し都度面積を積算	中間状態の幅を誤ってカウント	同じxのイベントは全てまとめて更新してから次のΔxを計算する
セグ木のリーフが「点」を表すと誤解	離散点RMQ問題と混同	リーフは隣接座標圧縮点の間の「幅」を表す
`cover_cnt`が0に戻った後も古い`covered_len`を使う	更新時のボトムアップ再計算を省略	区間加算のたびに必ず`covered_len`を再計算する
面積0の退化矩形を考慮せずコードを書く	制約$y_1<y_2$を前提にする	本問題では保証されるが一般化時は要注意

次のステップ

発展: 面積だけでなく「和集合の周囲長」を同時に求める（水平・垂直それぞれ独立したスイープが必要）
次回予告: 未定（Master Level ローテーションで次回選定）

自己評価

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

Day 126-Q5 — Klee's Measure Problem（矩形群の合併面積）

問題