題目描述: 給定若干個軸對齊的矩形,每個矩形由左下角 (x1, y1) 和右上角 (x2, y2) 定義。計算所有矩形覆蓋的總面積(重疊部分只計算一次)。結果對 10^9+7 取模。
解題思路:
時間複雜度:O(n^2 log n) — n 為矩形數量。座標壓縮後最多 2n 個 x 區間,每個事件需遍歷 x 區間。排序 O(n log n)
空間複雜度:O(n) — 存儲壓縮座標和事件
1. Collect all unique x-coordinates, sort and deduplicate 2. For each rectangle, create two events: - Open event at y1 (bottom edge): mark x-interval [x1, x2] - Close event at y3 (top edge): unmark x-interval [x1, x2] 3. Sort events by y-coordinate 4. Sweep from bottom to top: a. For current y, compute covered x-length from count array b. Area contribution = covered_x_length * (curY - prevY) c. Process all events at curY: increment/decrement count for x-intervals d. Update prevY = curY 5. Return total area mod 10^9+7
線段樹優化掃描線:用線段樹維護 x 軸上的覆蓋長度,每次事件更新為 O(log n),整體時間複雜度降為 O(n log n)。適合矩形數量很大的情況。
容斥原理:直接計算所有矩形面積之和,減去兩兩交集,加上三三交集...但矩形數量多時,交集的組合數爆炸,不如掃描線高效。僅適合矩形極少的情況。