POJ 2528 Mayor's Posters：離散化 + 線段樹區間覆蓋統計可見海報

POJ 2528「Mayor's Posters」：10⁷ 長度的牆，n≤10000 張海報依次貼上（覆蓋）。求最終可見海報數。本文解析坐標離散化 + 線段樹區間賦值 + 遍歷統計的標準解法。

問題建模

• 牆長 10⁷，海報 n ≤ 10000。
• 海報 i 覆蓋區間 [li, ri]（整數端點，閉區間）。
• 後貼覆蓋先貼 → 區間賦值操作，值為海報編號。
• 最終統計有多少不同海報編號出現在牆上。

離散化必要性

直接建 10⁷ 線段樹節點過大（內存/時間）。但只有 2n ≤ 20000 個關鍵端點，可離散化。

離散化技巧：保持相鄰關係

若只離散端點，區間內部間隙會丟失。解決：對所有端點排序，若相鄰端點差 > 1，插入中間值。

// 收集所有端點
vector<int> coords;
for (each poster) coords.push_back(l), coords.push_back(r);
sort, unique;

// 補充間隙
vector<int> all = coords;
for (int i = 0; i+1 < coords.size(); ++i) {
    if (coords[i+1] > coords[i] + 1)
        all.push_back(coords[i] + 1); // 插入中間代表點
}
sort, unique(all);
// 映射：原坐標 -> 離散索引 (1-based)
map<int,int> mp; // 或二分查找
for (int i = 0; i < all.size(); ++i) mp[all[i]] = i+1;

線段樹區間賦值

• 節點存 color（海報編號），0 表示無/混合。
• 懶標記 tag：區間統一賦值。
• 更新：update(L, R, poster_id)。

關鍵代碼

void pushdown(int rt) {
    if (tag[rt]) {
        tag[ls] = tag[rs] = tag[rt];
        color[ls] = color[rs] = tag[rt];
        tag[rt] = 0;
    }
}

void update(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && r <= R) {
        color[rt] = tag[rt] = c;
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (L <= mid) update(L, R, c, l, mid, ls);
    if (R > mid) update(L, R, c, mid+1, r, rs);
}

void query(int l, int r, int rt) {
    if (color[rt]) {
        if (!vis[color[rt]]) { ans++; vis[color[rt]] = 1; }
        return;
    }
    if (l == r) return;
    pushdown(rt);
    int mid = (l + r) >> 1;
    query(l, mid, ls);
    query(mid+1, r, rs);
}

完整流程

1. 讀入海報區間，收集端點並離散化（含補間隙）。
2. 建線段樹，大小 = 離散後坐標數。
3. 按輸入順序依次 update 每張海報。
4. 遍歷線段樹收集所有出現的 color > 0，去重計數。
5. 輸出答案。

複雜度

• 離散化：O(n log n)
• n 次更新：O(n log n)
• 遍歷統計：O(離散大小) = O(n)
• 總時間：O(n log n)，空間：O(n)

關鍵細節總結

1. 離散化必須補間隙：否則相鄰離散點間的原始區間會合併，導致覆蓋關係錯誤。
2. 海報編號從 1 開始：0 保留給「無/混合」。
3. 查詢時去重：用 vis[] 數組標記已計數海報。
4. 多測試用例：每用例重置所有數據結構。

總結

本題是「大坐標範圍 + 少量操作」的經典離散化 + 線段樹應用。核心難點在於正確離散化保持區間拓撲關係。掌握「收集端點 → 排序去重 → 補間隙 → 映射」流程，可解決所有類似問題。