POJ 2528 Mayor's Posters 題解：線段樹 + 離散化

題目大意

有一面長 10,000,000 字節的牆壁，依次貼上 n（≤10,000）張海報，每張海報覆蓋連續區間 [l_i, r_i]。後貼的海報會覆蓋前者。求最終可見的海報數量（至少有一字節可見即算可見）。

核心思路

1. 坐標離散化：牆壁長度極大但海報數較少，僅需關注所有海報的端點。將所有 l_i, r_i 收集、排序、去重，映射到 0..m-1。
2. 逆序處理 + 線段樹區間覆蓋查詢：從最後一張海報向前遍歷。對於當前海報對應的離散化區間，查詢線段樹中該區間是否已被完全覆蓋；若未完全覆蓋，則該海報可見，計數器加一，並將該區間標記為已覆蓋。線段樹需支持區間賦值（懶標記）與區間查詢（是否全覆蓋）。

關鍵技術點

• 離散化時需保留端點原始順序關係，通常將區間映射為離散索引區間 [L, R]。
• 線段樹節點維護 cover 標記：1 表示該區間已被完全覆蓋。pushdown 時將標記下傳給子節點。
• 查詢函數 query(pos, L, R) 返回 1 表示該區間有未覆蓋部分（即海報可見），並將該區間標記為覆蓋；返回 0 表示已完全覆蓋。

兩種實現對比

文中給出兩份代碼，第一份在 query 入口直接判斷 f[pos].cover，第二份移除該判斷改用 pushdown。第一份邏輯更直觀且正確；第二份若缺少入口判斷會導致重複計數。建議採用第一種寫法。

複雜度分析

• 離散化：O(n log n)
• 線段樹構建：O(m)，m ≤ 2n
• 每張海報一次查詢+更新：O(log m)
• 總時間：O(n log n)，空間：O(m)，完全滿足限制。

參考代碼片段（核心邏輯）

int query(int pos, int L, int R) {
    if (f[pos].cover) return 0;               // 已全覆蓋
    if (f[pos].le == L && f[pos].ri == R) {   // 精確匹配區間
        f[pos].cover = 1;
        return 1;                             // 可見
    }
    int mid = (f[pos].le + f[pos].ri) >> 1;
    int res = 0;
    if (mid >= R) res = query(L(pos), L, R);
    else if (mid < L) res = query(R(pos), L, R);
    else res = query(L(pos), L, mid) | query(R(pos), mid+1, R);
    if (f[L(pos)].cover && f[R(pos)].cover) f[pos].cover = 1;
    return res;
}