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

題目核心

長度 10⁷ 的牆面，依序貼 n ≤ 10⁴ 張海報（區間 [lᵢ, rᵢ]，後貼蓋過前貼）。求最終可見海報數（至少露出 1 個單位段）。

離散化：避免 10⁷ 陣列

直接建 10⁷ 線段樹記憶體超限。利用「只有端點位置重要」的性質，將所有 lᵢ, rᵢ 收集、排序、去重。但相鄰離散座標間可能有間隙，若間隙 > 1，中間整段牆面行為一致，必須保留。標準做法：

1. 收集所有 lᵢ, rᵢ 至 xs[]，排序去重。
2. 對每對相鄰 xs[i], xs[i+1]，若 xs[i+1] > xs[i] + 1，插入 xs[i] + 1 作為「間隙代表點」。
3. 最終離散點數 ≤ 2n + (2n-1) = 4n ≈ 4 萬，線段樹節點 4 × 4n ≈ 1.6×10⁵，極安全。

線段樹：區間賦值 + 顏色查詢

• 節點值 cover：-1 表示混合色，≥0 表示整段為單一海報編號（0 代表無）。
• 下推：pushDown 將父節點顏色強制傳給兩子節點。
• 插入：區間 [L, R] 染色 id，標準 lazy propagation。
• 查詢：遍歷整棵樹，遇 cover ≥ 0 即標記 vis[cover] = true 並返回（無需遞迴子樹），最後統計 vis[] 中 true 個數（忽略 0）。

完整流程

for each test case:
    read n
    collect all l[i], r[i] into xs
    discretize xs with gap filling
    build segment tree on [0, xs.size()-2]  // 每個單位段對應一個葉子
    for i = 1..n:
        L = lower_bound(xs, l[i])
        R = lower_bound(xs, r[i]) - 1     // 單位段索引
        update(L, R, i)
    query whole tree -> count vis[id]
    output count

常見坑點

• 區間映射：海報 [l, r] 覆蓋單位段 [l, r-1]，離散後索引需對應「單位段」而非端點。
• 去重後大小：Hash 陣列需 unsigned short（≤ 65535），short 會溢位導致 RE。
• 多測資清理：每組 memset(cover, -1)、vis[] = false、xs.clear()。

總結

本題是「離散化 + 線段樹區間染色」的經典模板。關鍵在於正確處理離散座標間的間隙，以及查詢時利用懶標記直接收集顏色而不下推到葉子，將查詢複雜度從 O(N) 降為 O(顏色數 × log N)。