POJ 2528 Mayor's Posters：線段樹區間覆蓋 + 離散化經典實戰

問題描述

有 n 張海報依次貼在牆上，每張海報覆蓋區間 [L, R]。後貼的海報會覆蓋前面的。求最終可見的海報數量（即至少有一點未被覆蓋的海報）。

約束：n ≤ 10,000，坐標範圍大（需離散化）。

核心思想：離散化 + 線段樹區間覆蓋

1. 離散化

收集所有端點 L, R+1（注意開區間處理），排序去重，映射到 1..M。
關鍵技巧：區間改為 [L, R+1)，避免相鄰海報邊界重疊判斷錯誤。

2. 線段樹區間賦值

• 節點存儲 cover：該區間被哪張海報完全覆蓋（0 表示混合/未覆蓋）。
• 更新時：若當前區間完全在更新範圍內，直接打標記 cover = poster_id，不再遞歸子節點（懶標記思想）。
• 下推：若父節點有 cover，向子節點傳遞並清空父節點。

3. 統計可見海報

遍歷線段樹葉子節點（或遞歸收集），將所有 cover > 0 的海報標記為可見，最後計數。

完整代碼實現

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 20010;

int cover[maxn << 2];  // 區間覆蓋標記：0=混合, >0=海報編號

struct Point {
    int x, id, v;  // x=原坐標, id=原序號, v=離散化後坐標
} b[maxn];

int n;

bool cmp1(Point a, Point b) { return a.x < b.x; }
bool cmp2(Point a, Point b) { return a.id < b.id; }

void build(int l, int r, int rt) {
    cover[rt] = 0;
    if (l + 1 == r) return;  // 葉子區間 [l, l+1) 對應單個離散段
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m, r, rt << 1 | 1);
}

// 區間賦值：將 [x, y) 設置為 num
void update(int x, int y, int l, int r, int rt, int num) {
    if (l == x && r == y) {
        cover[rt] = num;
        return;
    }
    int m = (l + r) >> 1;
    // 下推懶標記
    if (cover[rt]) {
        cover[rt << 1] = cover[rt];
        cover[rt << 1 | 1] = cover[rt];
        cover[rt] = 0;
    }
    if (y <= m) update(x, y, l, m, rt << 1, num);
    else if (x >= m) update(x, y, m, r, rt << 1 | 1, num);
    else {
        update(x, m, l, m, rt << 1, num);
        update(m, y, m, r, rt << 1 | 1, num);
    }
}

// 遍歷收集可見海報
void query(int l, int r, int rt, bool *vis) {
    if (l + 1 == r || cover[rt]) {
        vis[cover[rt]] = true;
        return;
    }
    int m = (l + r) >> 1;
    if (cover[rt]) {
        cover[rt << 1] = cover[rt];
        cover[rt << 1 | 1] = cover[rt];
        cover[rt] = 0;
    }
    query(l, m, rt << 1, vis);
    query(m, r, rt << 1 | 1, vis);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &b[i<<1].x, &b[i<<1|1].x);
            b[i<<1|1].x++;  // 關鍵：R -> R+1，構造左閉右開區間
            b[i<<1].id = i << 1;
            b[i<<1|1].id = i << 1 | 1;
        }
        
        // 離散化
        sort(b, b + 2*n, cmp1);
        int now = b[0].x, sum = 1;
        for (int i = 0; i < 2*n; i++) {
            if (b[i].x != now) { now = b[i].x; sum++; }
            b[i].v = sum;
        }
        sort(b, b + 2*n, cmp2);  // 恢復原順序
        
        build(1, sum, 1);
        
        // 依次貼海報
        for (int i = 0; i < n; i++) {
            update(b[i<<1].v, b[i<<1|1].v, 1, sum, 1, i + 1);
        }
        
        // 統計可見
        static bool vis[maxn];
        memset(vis, 0, sizeof(vis));
        query(1, sum, 1, vis);
        
        int ans = 0;
        for (int i = 1; i <= n; i++) if (vis[i]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

關鍵技術點深度解析

1. 為什麼用 `R+1` 構造左閉右開區間？

海報覆蓋 [L, R]。若直接離散化 L, R，相鄰海報 [1,2] 和 [3,4] 在離散座標可能相鄰，導致邊界判斷混淆。
使用 [L, R+1) 後，每個離散段代表原坐標軸上的一個基本區間，海報覆蓋恰好是若干基本區間的並，邊界天然分離。

2. 線段樹區間賦值的懶標記優化

• 不維護「子節點信息合併」，只維護「整段被誰覆蓋」。
• 更新時若完全覆蓋，直接打標記返回，不遞歸到底。
• 查詢/下推時才將標記推給子節點。
• 時間複雜度：O((n + M) log M)，M ≤ 2n。

3. 內存佈局

• maxn = 20010 → 線段樹大小 maxn << 2 = 80040 足夠。
• cover 用 int 存海報編號（1-based），0 表示無整體覆蓋。

測試樣例

輸入：
1
3
1 4
2 5
3 6

離散化端點：1,5, 2,6, 3,7 → 排序：1,2,3,5,6,7
區間映射：[1,5) [2,6) [3,7)
貼海報 1,2,3 後，可見海報為 3 張（每張都有獨有區間）。

總結

POJ 2528 是線段樹區間覆蓋 + 離散化的教科書級題目。核心考點：

1. 離散化時處理邊界（R+1 技巧）。
2. 線段樹懶標記實現區間賦值（非增量更新）。
3. 最終統計時遍歷收集非零標記。

此模板可直接應用於「區間塗色最後顏色數」「海報覆蓋」「區間賦值查詢」等問題。代碼結構清晰、邊界處理嚴謹，是競程必備模板之一。