HDU 1542 Atlantis 詳解：線段樹求矩形面積並

題目大意

給定 n 個矩形（邊平行於座標軸），求它們覆蓋的總面積（重疊區域僅計算一次）。

核心算法：掃描線 + 線段樹

經典「矩形面積並」解法：

1. 離散化 Y 座標：收集所有矩形的下邊 y1 和上邊 y2，排序去重，構建離散座標陣列 ys[]。
2. 構建掃描線事件：每個矩形產生兩條水平掃描線：
   • 下邊：x = x1, y ∈ [y1, y2), type = +1（進入）
   • 上邊：x = x2, y ∈ [y1, y2), type = -1（離開）
3. 按 x 排序事件，從左向右掃描。
4. 線段樹維護 Y 軸覆蓋長度：節點存儲覆蓋計數 cover 與覆蓋長度 len。更新區間時：
   • cover > 0 → 完全覆蓋，len = ys[r+1] - ys[l]
   • cover == 0 且非葉子 → len = left.len + right.len
   • 葉子且 cover == 0 → len = 0
5. 累加面積：相鄰兩事件間 Δx × 當前總覆蓋長度。

關鍵實現細節

離散化與區間映射

離散座標 ys[] 大小為 m，線段樹維護 m-1 個基本區間 [ys[i], ys[i+1])。更新區間 [y1, y2) 對應線段樹區間 [L, R-1]，其中 L = lower_bound(ys, y1), R = lower_bound(ys, y2)。

線段樹節點結構

struct SegNode {
    int cover;      // 覆蓋計數
    double len;     // 覆蓋長度
} tree[MAXN << 2];

PushUp 邏輯

void pushUp(int o, int l, int r) {
    if (tree[o].cover > 0) {
        tree[o].len = ys[r+1] - ys[l];  // 完全覆蓋
    } else if (l == r) {
        tree[o].len = 0;                // 葉子無覆蓋
    } else {
        tree[o].len = tree[o<<1].len + tree[o<<1|1].len;  // 合併子節點
    }
}

複雜度分析

• 離散化：O(n log n)
• 事件排序：O(n log n)
• 線段樹操作：O(n log n)（每個事件一次更新）
• 總體：O(n log n) 時間，O(n) 空間

常見坑點

1. 區間右端點開區間：矩形上邊不計入面積，避免相鄰矩形重複計算邊界。
2. double 精度：座標與面積用 double，輸出格式控制精度。
3. 多測試用例：每輪需重置線段樹、離散化陣列、事件列表。

總結

掃描線 + 線段樹是矩形面積並、周長並、重疊矩形計數等幾何問題的通用框架。關鍵在於正確離散化、區間映射與線段樹覆蓋長度維護邏輯。HDU 1542 是該模板的經典應用題。