https://www.luogu.com.cn/problem/P5490

題目描述

求 $n$ 個四邊平行于坐標軸的矩形的面積并。

輸入格式

第一行一個正整數 $n$。

接下來 $n$ 行每行四個非負整數 $x_1,y_1,x_2,y_2$，表示一個矩形的四個端點坐標為 $(x_1,y_1),(x_1,y_2),(x_2,y_2),(x_2,y_1)$。

輸出格式

一行一個正整數，表示 $n$ 個矩形的并集覆蓋的總面積。

輸入輸出樣例 #1

輸入 #1

2
100 100 200 200
150 150 250 255

輸出 #1

18000

說明/提示

對于 $20\%$ 的數據，$1\le n\le 1000$。
對于 $100\%$ 的數據，$1\le n\le {10}^5$，$0\le x_1<x_2\le {10}^9$，$0\le y_1<y_2\le {10}^9$。

🚀 C++ 代碼實現

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct Event {int x, y1, y2, type; // x 坐標, y 起點, y 終點, type=1(加入), type=-1(刪除)Event(int x, int y1, int y2, int type) : x(x), y1(y1), y2(y2), type(type) {}
};struct SegmentTree {// y 軸區間被覆蓋次數機覆蓋長度vector<int> cnt, len;// 存儲離散化后的 y 坐標值，用于映射 y 軸上的真實值到線段樹的索引vector<int> y_coords;SegmentTree(int size) {cnt.resize(size * 4);len.resize(size * 4);}void build(int l, int r, int idx) {cnt[idx] = len[idx] = 0;if (l + 1 == r) return;int mid = (l + r) / 2;build(l, mid, idx * 2);build(mid, r, idx * 2 + 1);}void update(int jobl, int jobr, int val, int l, int r, int idx) {if (jobl >= r || jobr <= l) return;if (jobl <= l && r <= jobr) {cnt[idx] += val;} else {int mid = (l + r) / 2;update(jobl, jobr, val, l, mid, idx * 2);update(jobl, jobr, val, mid, r, idx * 2 + 1);}// 計算當前區間的 y 方向被覆蓋的長度if (cnt[idx] > 0) {len[idx] = y_coords[r] - y_coords[l];  // 計算該段區間長度} else {len[idx] = (l + 1 == r) ? 0 : (len[idx * 2] + len[idx * 2 + 1]);  // 合并子區間}}
};int main() {int n;cin >> n;vector<Event> events;vector<int> y_coords;// 讀取矩形數據for (int i = 0; i < n; i++) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;events.emplace_back(x1, y1, y2, 1);  // 左邊界events.emplace_back(x2, y1, y2, -1); // 右邊界y_coords.push_back(y1);y_coords.push_back(y2);}// 對 y 坐標進行離散化sort(y_coords.begin(), y_coords.end());y_coords.erase(unique(y_coords.begin(), y_coords.end()), y_coords.end());// 給事件按照 x 軸排序sort(events.begin(), events.end(), [](const Event &a, const Event &b) {return a.x < b.x;});// 初始化線段樹SegmentTree segTree(y_coords.size());segTree.y_coords = y_coords;segTree.build(0, y_coords.size() - 1, 1);long long area = 0;for (size_t i = 0; i < events.size() - 1; i++) {int x = events[i].x;int y1 = lower_bound(y_coords.begin(), y_coords.end(), events[i].y1) - y_coords.begin();int y2 = lower_bound(y_coords.begin(), y_coords.end(), events[i].y2) - y_coords.begin();segTree.update(y1, y2, events[i].type, 0, y_coords.size() - 1, 1);// 計算面積增量int dx = events[i + 1].x - x;area += 1LL * dx * segTree.len[1];  // 累加當前 x 范圍的面積}cout << area << endl;return 0;
}

🌟 解法思路：掃描線 + 線段樹

核心思想：

1. 轉換為掃描線問題：

   • 把每個矩形拆成兩條豎直邊（左邊界 + 右邊界）。
   • 每條邊記錄 x 坐標、y 區間以及是左邊界（加入）還是右邊界（刪除）。

2. 按 x 坐標排序：

   • 依次處理 x 變化的位置，維護 y 方向的覆蓋情況。

3. 使用線段樹維護 y 方向的覆蓋長度：

   • 統計當前 x 坐標下 y 方向被覆蓋的總長度。
   • 在 x 變化時，用 dx * covered_length 計算新增的面積。

📌 代碼解析

1. 讀取輸入并創建事件

   • 每個矩形 (x1, y1, x2, y2) 被拆成兩個事件：
     • 左邊界：(x1, y1, y2, +1)
     • 右邊界：(x2, y1, y2, -1)

2. 離散化 y 軸

   • y 軸可能范圍很大，使用排序+去重將 y 壓縮成 [0, m-1] 范圍。

3. 排序事件

   • 按照 x 軸排序，保證掃描順序是從左到右。

4. 掃描線遍歷

   • 遍歷 x 方向的邊界事件，更新 y 方向的覆蓋長度。
   • 計算當前 x 范圍的面積增量 dx * covered_length。

5. 線段樹維護 y 方向覆蓋情況

   • update(y1, y2, type) 更新 cnt 計數。
   • len[1] 存儲 y 方向被覆蓋的總長度。

---

📊 復雜度分析

• 事件排序：$O(N\log N)$
• 線段樹更新：$O(N\log N)$
• 總時間復雜度：$O(N\log N)$

---

? 適用場景

• 計算多個矩形的面積并
• 計算建筑投影面積
• 計算不規則區間合并

📌 該方法適用于 N ≤ 10^5 的情況，效率極高！🚀

---

在線段樹的構建過程中，我們通常將一個區間 [l, r] 拆分，直到無法繼續拆分為止。
在很多常見的線段樹應用（如單點更新、區間查詢）中，葉子節點往往是 l == r，但是在掃描線+線段樹這種應用場景下，我們的離散化 y 坐標并不連續，因此葉子節點的定義有所不同，l + 1 == r 才是葉子節點，而不是 l == r。

---

🌟 為什么 l + 1 == r 才是葉子節點？

離散化的線段樹是基于區間而不是單個點。

• 常規線段樹（連續區間）：

  • 例如求區間最小值、區間和，通常是 l == r 作為葉子節點。
  • 但在這里，我們是計算“區間長度”，所以葉子節點應該是最小單位的區間 [y_coords[l], y_coords[r]]，而不是單個點。

• 離散化線段樹（區間合并）：

  • 葉子節點應該是最小的 y 軸區間，而 l == r 只表示單個坐標，不是一個“區間”。
  • 當 l + 1 == r，意味著 y_coords[l] 到 y_coords[r] 之間已經沒有更多的離散坐標，可以認為它們形成了最小單位的“區間”，無法再繼續細分，因此它是葉子節點。

---

🔹 詳細舉例

1?? 假設 y_coords = {2, 5, 10, 15}

離散化后的 y_coords 索引：

y 值	離散索引
2	0
5	1
10	2
15	3

表示的區間：

區間 [0,1] 表示 y = [2, 5]
區間 [1,2] 表示 y = [5, 10]
區間 [2,3] 表示 y = [10, 15]

---

2?? 線段樹的構造

構建線段樹時，我們遞歸拆分區間 [0,3]：

          [0,3]/     \[0,2]   [2,3]/     \[0,1]   [1,2]

在這棵樹中：

1. [0,1] 表示 [2,5]，是葉子節點（因為 0+1 == 1）
2. [1,2] 表示 [5,10]，是葉子節點（因為 1+1 == 2）
3. [2,3] 表示 [10,15]，是葉子節點（因為 2+1 == 3）

---

3?? 為什么 l + 1 == r 作為葉子節點，而 l == r 不行？

如果 l == r 作為葉子節點，那就會出現 l = 0, r = 0 這種情況，這樣的區間沒有物理意義，因為：

• y_coords[0] = 2 只是一個點，并不能表示一個范圍。
• 但 y_coords[0] 到 y_coords[1] ([2,5]) 形成了一個“區間”，才有意義。

所以，葉子節點的最小單位應該是 [y_coords[l], y_coords[r]]，而不是單個點。

---

? 結論

方式	葉子節點定義	適用情況	是否適用于掃描線+線段樹
l == r	單個點	適用于連續值（如 RMQ、區間和）	? 不適用于離散區間
l + 1 == r	一個離散區間	適用于離散化的線段樹（掃描線）	? 適用

---

📌 代碼示例

if (l + 1 == r) { // 葉子節點len[idx] = 0;  // 初始狀態下沒有被覆蓋
} else { // 非葉子節點，合并左右子樹len[idx] = len[idx * 2] + len[idx * 2 + 1];
}

---

🎯 總結

• 線段樹的葉子節點是最小單位的“區間”而不是單點，所以 l + 1 == r 作為葉子節點。
• 常規線段樹 l == r 適用于單點查詢，但掃描線 + 線段樹需要處理區間，所以 l + 1 == r 作為葉子節點。
• 這樣，我們才能用 y_coords[r] - y_coords[l] 計算被覆蓋的區間長度，否則 l == r 沒有意義。

🚀 這樣就能理解為什么 l + 1 == r 是葉子節點，而 l == r 不行了！

掃描線相關練習題目

• 218. 天際線問題
• P1904 天際線