POJ 3277 City Horizon：線段樹維護建築物剪影面積

題目大意

N 棟矩形建築 (N ≤ 40000)，第 i 棟橫跨 [A_i, B_i]，高度 H_i。建築可重疊。求天際線剪影總面積。坐標 ≤ 1e9，高度 ≤ 1e9。

離線離散化 + 線段樹

1. 坐標離散化： 收集所有 A_i, B_i，排序去重。將大坐標映射到 1..M (M ≤ 80000)。
2. 線段樹維護區間最大高度：
   • 葉子節點對應基本區間 [x_i, x_{i+1})。
   • 節點存 `maxHeight` (區間最大高度)，`cover` 標記 (是否被完全覆蓋)。
   • 插入建築：區間更新最大值。若節點區間完全被建築覆蓋且新高度 ≥ 當前高度，直接更新 `maxHeight` 並打標記 `cover=1` (子孫無需更新)。
3. 統計面積： 遍歷線段樹葉子，面積累加 `height * (x_{i+1} - x_i)`。

關鍵代碼片段 (C++)

struct Node { int l, r; int h; bool cover; } tree[MAXN * 4];
int xs[MAXN * 2]; // 離散化坐標

void insert(int L, int R, int h, int rt) {
    if (tree[rt].l == L && tree[rt].r == R) {
        if (tree[rt].h < h) tree[rt].h = h;
        tree[rt].cover = true;
        return;
    }
    if (tree[rt].cover) return; // 已被更高建築完全覆蓋
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    if (R <= mid) insert(L, R, h, rt<<1);
    else if (L >= mid) insert(L, R, h, rt<<1|1);
    else { insert(L, mid, h, rt<<1); insert(mid, R, h, rt<<1|1); }
}

long long query(int rt) {
    if (tree[rt].l + 1 == tree[rt].r) { // 葉子：基本區間
        return 1LL * tree[rt].h * (xs[tree[rt].r] - xs[tree[rt].l]);
    }
    if (tree[rt].cover) { // 整段同高
        return 1LL * tree[rt].h * (xs[tree[rt].r] - xs[tree[rt].l]);
    }
    return query(rt<<1) + query(rt<<1|1);
}

優化細節

• 離散化後基本區間為 `[xs[i], xs[i+1])`，線段樹葉子對應此區間。
• `cover` 標記實現「區間賦值最大值」的懶傳播：若父節點已被高度 H 完全覆蓋，子孫無需再更新 (因後續建築高度 ≤ H 不會改變最大值，>H 會在父節點直接攔截)。
• 面積計算用 `long long` (64位)，單棟面積可達 1e18。

複雜度

• 離散化：O(N log N)
• N 次區間更新：O(N log M)
• 一次遍歷統計：O(M)
• 總體：O(N log N)，N=40000 極快。