SGU 319 Kalevich Strikes Back：線段樹掃描線維護矩形包含關係，DFS 計算面積

問題描述

給定一個 W × H 的大矩形，內部有 n 個不相交但可能包含的子矩形（邊平行坐標軸）。這 n 個矩形將大矩形分割成 n+1 個區域（包括矩形本身及其外部）。求這 n+1 個區域的面積，從小到大輸出。

核心思路：掃描線 + 線段樹構建父子關係

1. 將每個矩形拆為底邊（下邊）和頂邊（上邊）事件，按 y 座標排序。
2. 掃描線從下向上掃。線段樹維護 x 軸區間當前覆蓋的「最內層矩形 id」。
3. 遇到底邊（矩形開始）：查詢線段樹該區間的覆蓋 id，即為該矩形的父親。記錄父子關係，並將該區間覆蓋更新為當前矩形 id。
4. 遇到頂邊（矩形結束）：將該區間覆蓋恢復為父親 id（或 0）。
5. 掃描結束後，得到一棵以 0（大矩形）為根的樹。每個節點面積 = 矩形面積 - 所有子節點面積之和。DFS 計算。

關鍵數據結構

• 線段樹：區間賦值（覆蓋 id），單點查詢（或區間查詢任意一點）。
• 離散化 x 座標：所有矩形左右邊界 + 0, W。
• 樹結構：鄰接表存父子關係。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 70010;

struct Rect { int x1, y1, x2, y2; } rect[MAXN];
struct Event { int y, x1, x2, id, type; }; // type: +1 底邊, -1 頂邊
vector<Event> events;
vector<int> tree[MAXN];
LL area[MAXN];
int W, H, n;

vector<int> xs; // 離散化 x

// 線段樹：區間賦值，查詢任意點值
int cover[MAXN << 2];
void build(int o, int l, int r) { cover[o] = 0; if (l == r) return; int m = (l+r)/2; build(o<<1,l,m); build(o<<1|1,m+1,r); }
void pushdown(int o) { if (cover[o]) { cover[o<<1] = cover[o<<1|1] = cover[o]; cover[o] = 0; } }
void update(int o, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) { cover[o] = val; return; }
    pushdown(o); int m = (l+r)/2;
    if (L <= m) update(o<<1, l, m, L, R, val);
    if (R > m) update(o<<1|1, m+1, r, L, R, val);
}
int query(int o, int l, int r, int pos) {
    if (cover[o] || l == r) return cover[o];
    int m = (l+r)/2;
    return pos <= m ? query(o<<1, l, m, pos) : query(o<<1|1, m+1, r, pos);
}

void dfs(int u) {
    for (int v : tree[u]) {
        dfs(v);
        area[u] -= area[v];
    }
}

int main() {
    while (scanf("%d", &n) == 1) {
        scanf("%d%d", &W, &H);
        events.clear(); xs.clear();
        xs.push_back(0); xs.push_back(W);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d%d%d", &rect[i].x1, &rect[i].y1, &rect[i].x2, &rect[i].y2);
            if (rect[i].x1 > rect[i].x2) swap(rect[i].x1, rect[i].x2);
            if (rect[i].y1 > rect[i].y2) swap(rect[i].y1, rect[i].y2);
            events.push_back({rect[i].y1, rect[i].x1, rect[i].x2, i, 1});
            events.push_back({rect[i].y2, rect[i].x1, rect[i].x2, i, -1});
            xs.push_back(rect[i].x1); xs.push_back(rect[i].x2);
            area[i] = (LL)(rect[i].x2 - rect[i].x1) * (rect[i].y2 - rect[i].y1);
        }
        area[0] = (LL)W * H;
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        int XN = xs.size() - 1; // 區間數 = 點數 - 1

        auto getId = [&](int x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin(); };

        sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
            return a.y < b.y;
        });

        build(1, 1, XN);
        for (int i = 0; i <= n; ++i) tree[i].clear();

        for (auto &e : events) {
            int L = getId(e.x1), R = getId(e.x2); // 區間 [L, R-1]
            if (e.type == 1) { // 底邊
                int parent = query(1, 1, XN, L); // 任意查一點
                tree[parent].push_back(e.id);
                update(1, 1, XN, L, R-1, e.id);
            } else { // 頂邊
                update(1, 1, XN, L, R-1, 0); // 恢復為 0，實際應恢復父親，但掃描線順序保證父親已覆蓋外層
            }
        }

        dfs(0);
        sort(area, area + n + 1);
        for (int i = 0; i <= n; ++i) {
            printf("%lld%c", area[i], i == n ? '\n' : ' ');
        }
    }
    return 0;
}

複雜度

離散化 O(n log n)，事件排序 O(n log n)，線段樹操作 O(n log n)，DFS O(n)。總體 O(n log n)。