POJ 2528 Mayor's Posters：線段樹區間修改 + 離散化處理大坐標

題目大意

牆長 10⁷，貼 n ≤ 10,000 張海報（區間 [L,R]），後貼蓋前貼。求最終可見海報數。

核心挑戰：坐標過大需離散化

直接建線段樹需 4×10⁷ 節點，內存爆炸。利用離散化將關鍵坐標映射到連續小整數。

離散化關鍵：保留間隙

單純離散端點會出錯。例：[1,10], [1,3], [5,10] → 離散後 1,3,5,10 映射為 1,2,3,4。
第一張蓋 [1,4]，第二張蓋 [1,2]，第三張蓋 [3,4]，最終只見 2 張，實際應 3 張。
解決：相鄰離散坐標差 > 1 時，插入中間值代表「間隙」。

完整流程

1. 收集所有 L, R 到數組 X
2. 排序去重
3. 掃描 X，若 X[i] > X[i-1] + 1，插入 X[i-1]+1
4. 再次排序，建立映射 坐標 → 索引
5. 線段樹區間賦值修改（懶標記 setv）
6. 最終遍歷線段樹統計不同 setv 值

關鍵代碼片段

// 離散化
vector X;
for (i=1..n) { X.push_back(L[i]); X.push_back(R[i]); }
sort(X); X.erase(unique(X), X.end());
int m = X.size();
for (i=1; i X[i-1] + 1) X.push_back(X[i-1] + 1);
sort(X); // 再次排序
m = X.size();

// 映射區間
int lc = lower_bound(X, L[i]) - X.begin() + 1;
int rc = lower_bound(X, R[i]) - X.begin() + 1;
update(lc, rc, i, 1, m, 1); // 區間賦值海報編號

// 線段樹節點：setv 為賦值標記（0 表示無）
void push_down(int o) {
    if (setv[o]) {
        setv[o<<1] = setv[o<<1|1] = setv[o];
        setv[o] = 0;
    }
}
void update(int L, int R, int v, int l, int r, int o) {
    if (L <= l && r <= R) { setv[o] = v; return; }
    push_down(o);
    int m = (l+r)>>1;
    if (L <= m) update(L, R, v, l, m, o<<1);
    if (m < R) update(L, R, v, m+1, r, o<<1|1);
}

// 統計可見海報
void query(int l, int r, int o) {
    if (setv[o]) { if (!vis[setv[o]]) { vis[setv[o]]=1; ans++; } return; }
    if (l == r) return;
    int m = (l+r)>>1;
    query(l, m, o<<1); query(m+1, r, o<<1|1);
}

複雜度

• 離散化：O(n log n)
• 線段樹操作：O(n log n)
• 空間：O(n) 節點數 ≤ 4 × 離散後大小 ≤ 4 × 40000