題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1884 [USACO12FEB] Overplanting S

Problem Statement

題目簡述

給定 NN 個矩形，求這些矩形覆蓋的總面積（重疊部分只計算一次）。

Constraints

約束條件

  • 1≤N≤10001 \le N \le 1000
  • 座標範圍 −108≤x1,y1,x2,y2≤108-10^8 \le x_1, y_1, x_2, y_2 \le 10^8

思路：矩形面積聯集

計算多個矩形的聯集面積是經典的幾何問題。由於座標範圍高達 10810^8，無法直接開二維陣列來標記每個座標點的覆蓋狀態。然而，矩形數量 NN 相對較小（最多 1000），這提示我們可以利用離散化或掃描線來壓縮空間與時間。

方法一：離散化 + 二維差分

如果座標範圍沒這麼大（例如 10310^3 以內），這題可以直接直接用二維差分標記每個矩形。但現在座標高達 10810^8，無法開這麼大的陣列。好在矩形數量只有 N≤1000N \le 1000，我們可以借鑑 P1496 火烧赤壁 的一維離散化思路，將其擴展到二維。

離散化：將無限平面壓縮為有限網格

收集所有矩形的左右邊界（X 座標）與上下邊界（Y 座標），分別去重排序後，原本巨大的座標平面就被切割成最多 2N×2N2N \times 2N 個不均勻的網格。在同一個網格內，任何一點的覆蓋狀態都是一樣的——只有全部被覆蓋，或完全沒被覆蓋兩種可能，不可能有部分覆蓋部分沒被覆蓋的情況。因此壓縮後，我們只需要關心這些網格即可。

壓縮網格與實際面積的對應關係

離散化後，原本的座標被映射為連續的整數索引（例如 1,2,3,…1, 2, 3, \dots）。在壓縮後的網格中，座標點 (i,j)(i, j) 代表的是一個區間：X 軸範圍是 [Xi,Xi+1)[X_i, X_{i+1})，Y 軸範圍是 [Yj,Yj+1)[Y_j, Y_{j+1})。這個網格的實際面積為 (Xi+1−Xi)×(Yj+1−Yj)(X_{i+1} - X_i) \times (Y_{j+1} - Y_j)。

二維差分：記錄矩形覆蓋

在壓縮後的網格上，我們可以用二維差分來標記每個矩形覆蓋了哪些網格。每個矩形對應到一個連續的壓縮區域。我們只需在矩形的四個角上做標記：左下角與右上角加一，左上角與右下角減一。這樣後續透過二維前綴和還原時，就能得到每個網格被覆蓋的次數。

前綴和還原與面積統計

完成所有矩形的差分標記後，對整個壓縮網格做二維前綴和，就能還原出每個網格的真實覆蓋次數。最後，遍歷所有網格：只要該網格被覆蓋過（次數大於 0），就把它的實際面積（寬度 ×\times 高度）加到答案中。

複雜度分析

  • 時間複雜度：O(N2)\mathcal{O}(N^2)。
    • 收集並排序座標需 O(Nlog⁡N)\mathcal{O}(N \log N)
    • 處理二維差分與前綴和需遍歷 O(N)×O(N)\mathcal{O}(N) \times \mathcal{O}(N) 的網格，故為 O(N2)\mathcal{O}(N^2)。
  • 空間複雜度：O(N2)\mathcal{O}(N^2)。需要建立大小為 2N×2N2N \times 2N 的二維差分陣列。

方法二：掃描線 + 線段樹

核心概念

想像一條垂直於 X 軸的直線從左至右掃過整個平面。當掃描線遇到矩形的左邊界時，該矩形在 Y 軸上的投影區間覆蓋次數會增加；遇到右邊界時則減少。相鄰兩條掃描線之間所掃過的面積，即為「當前 Y 軸被覆蓋的總長度」乘上「兩條掃描線的 X 座標差」。

為了在掃描線推進時即時結算面積，我們需要動態維護「此刻 Y 軸上被覆蓋的總長度」。矩形的進入與離開，都等價於對某段 Y 區間做「+1 / -1」的區間加法。

由於座標範圍極大，必須先把所有矩形用到的 Y 座標離散化，將 Y 軸切成一段段基本區間（每段都是形如 [Yi,Yi+1)[Y_i, Y_{i+1}) 的半開區間）。接著用線段樹管理這些基本區間的覆蓋狀態，並在任何時刻都能查到整條 Y 軸的覆蓋總長。

線段樹該維護什麼資訊？

直覺上可以嘗試直接維護「被覆蓋的長度」，但重疊會使狀態難以從子節點乾淨地合併：同一段區間可能被覆蓋多層，減掉一層後仍然應該算覆蓋，這類資訊如果只存一個長度，很難在區間加減後快速正確更新。

因此更常見、也更穩定的做法是換個角度：不直接追「覆蓋長度」，而是追「未覆蓋長度」。換句話說，我們想知道整條 Y 軸上，覆蓋次數為 00 的部分有多長。

節點資訊的意義

每個節點對應一段連續的 Y 範圍（由多個基本區間組成），我們希望它能回答：「這段範圍內最薄的地方被覆蓋了幾層？而達到這個最薄層數的區域，總長是多少？」

在線段樹的每個節點中，我們維護兩個關鍵量：

  • 區間內的最小覆蓋次數：代表該節點所管轄的 Y 軸範圍內，最薄弱的覆蓋層數。
  • 該最小值對應的區段總長度：在該節點管轄範圍內，所有覆蓋次數恰好等於「最小覆蓋次數」的基本區段長度總和。

有了這兩個量，只看根節點（代表整條 Y 軸）就能把「覆蓋總長」推回來：

從根節點推導覆蓋長度

設 LL 為整條 Y 軸總長（也就是 Ymax⁡−Ymin⁡Y_{\max} - Y_{\min}）。

  • 若最小覆蓋次數為 00，則「最小值對應的總長度」就是未覆蓋長度，覆蓋長度為 L−未覆蓋長度L - \text{未覆蓋長度}。
  • 若最小覆蓋次數大於 00，表示不存在覆蓋次數為 00 的區域，覆蓋長度直接等於 LL。

這套設計特別適合搭配 Lazy Tag：區間整體「+1 / -1」時，該區間每個基本段的覆蓋次數都一起平移，因此「最小覆蓋次數」會整體加上變化量，而「哪些地方達到最小值」的分布不會因為整體平移而改變，對應的總長度也就不需要調整。這使得區間修改非常乾淨。

最後，將每個矩形的左、右邊界視為事件並依 X 座標排序。掃描線在兩個相鄰事件 X 座標之間前進的距離，乘上「此刻的覆蓋總長」，就是這段垂直條帶對答案的貢獻；接著再把該 X 座標上的所有 Y 區間事件套用到線段樹，讓狀態與下一段條帶對齊。

複雜度分析

  • 時間複雜度：O(Nlog⁡N)\mathcal{O}(N \log N)。排序事件與 Y 座標需 O(Nlog⁡N)\mathcal{O}(N \log N)，共有 2N2N 個事件，每次事件對線段樹進行區間修改需 O(log⁡N)\mathcal{O}(\log N)。
  • 空間複雜度：O(N)\mathcal{O}(N)。線段樹與事件陣列的大小皆與 NN 成正比。

Code

方法一：離散化 + 二維差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def solve():
    q = int(input())
    rects = []

    Xs = set()
    Ys = set()

    for _ in range(q):
        x1, y1, x2, y2 = map(int, input().split())
        assert x1 <= x2 and y2 <= y1
        # 整理成左下/右上邊界
        rects.append((x1, y2, x2, y1))
        Xs.add(x1)
        Xs.add(x2)
        Ys.add(y2)
        Ys.add(y1)

    # 離散化
    Xs = sorted(Xs)
    Ys = sorted(Ys)
    mpX = {x: i for i, x in enumerate(Xs, start=1)}
    mpY = {y: i for i, y in enumerate(Ys, start=1)}

    n, m = len(Xs), len(Ys)

    # diff[i][j] 表示壓縮座標點上的差分
    diff = [[0] * (m + 1) for _ in range(n + 1)]

    # 二維差分更新
    for x1, y1, x2, y2 in rects:
        diff[mpX[x1]][mpY[y1]] += 1
        diff[mpX[x2]][mpY[y1]] -= 1
        diff[mpX[x1]][mpY[y2]] -= 1
        diff[mpX[x2]][mpY[y2]] += 1

    # 二維前綴和還原矩陣
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]

    # 計算面積
    ans = 0
    for i in range(1, n):
        dx = Xs[i] - Xs[i - 1]
        for j in range(1, m):
            dy = Ys[j] - Ys[j - 1]
            if diff[i][j] > 0:
                ans += dx * dy
    print(ans)


if __name__ == "__main__":
    solve()

方法二：掃描線 + 線段樹

為了程式碼簡潔以及方便理解，這裡以 AtCoder Library (ACL) 的 LazySegTree 為模板，但 Luogu 的環境中不包含 ACL，提交時請自行替換為 ACL 中的原始程式碼或自己的實現方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from collections import defaultdict
from itertools import pairwise

# Luogu 的環境沒有 atcoder library，提交時請替換為 LazySegTree 的原始程式碼
from atcoder.lazysegtree import LazySegTree


def solve():
    n = int(input())

    events = defaultdict(list)
    Ys = set()
    for _ in range(n):
        # 整理成左下/右上邊界
        x1, y2, x2, y1 = map(int, input().split())
        events[x1].append((y1, y2, 1))
        events[x2].append((y1, y2, -1))
        Ys.add(y1)
        Ys.add(y2)

    events = sorted(events.items())

    Ys = sorted(Ys)
    mp = {y: i for i, y in enumerate(Ys)}  # 0-indexed

    # data[i] 代表區間 [ys[i], ys[i + 1]) 的 (最小覆蓋次數, 對應長度)
    data = [(0, y2 - y1) for y1, y2 in pairwise(Ys)]
    tot_y = Ys[-1] - Ys[0]

    def op(a, b):
        if a[0] < b[0]:
            return a
        if a[0] > b[0]:
            return b
        return (a[0], a[1] + b[1])

    def mapping(f, x):
        # 區間覆蓋次數整體 + f，最小覆蓋次數會改變，但對應長度不變
        return (x[0] + f, x[1])

    def composition(f, g):
        return f + g

    seg = LazySegTree(op, (float("inf"), 0), mapping, composition, 0, data)

    ans = 0
    prev_x = events[0][0]
    for x, es in events:
        min_cover, min_cover_len = seg.all_prod()
        covered_y = tot_y - (min_cover_len if min_cover == 0 else 0)
        ans += covered_y * (x - prev_x)
        prev_x = x
        for y1, y2, delta in es:  # [y1, y2)
            seg.apply(mp[y1], mp[y2], delta)

    print(ans)


if __name__ == "__main__":
    solve()