【題目敘述】https://vjudge.net/problem/POJ-2528
【相同題目】UVA 10587 Mayor’s posters
【解題想法】線段樹 (Segment Tree)，數據離散化
- l[i], r[i]：「海報-i」的左界和右界。數字很大，先進行離散化處理，節省記憶體空間。
- size[i]：「海報-i」的的能見範圍，初始值為海報原尺寸 (寬度)。
- t[ ]：暫存用，數據去重及離散化。（開兩倍陣列）
- wall[ ]：線段樹。（開t[ ]的四倍陣列）
- wall[x] = -1：初始值，表示區間 (seg-x) 尚未張貼任何海報。
- wall[x] = 0：表示區間 (seg-x) 貼有兩張或更多的海報。
- wall[x] = p (1 <= p <= n)：表示區間 (seg-x) 被「海報-p」佈滿。
- 函式 update( )：線段樹的區間改值。
- 張貼新海報之前，先重新計算原海報的能見範圍。
- wall[x] = p：區間 (seg-x) 貼上「新海報-p」。（Line-38）
- 函式 cover( )：處理舊海報被新海報覆蓋。
- 影響原海報的能見範圍：size[wall[x]] -= R – L + 1; (Line-26)
- 下圖以sample input 為例：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int c, n, m, ans;
int l[maxn], r[maxn], size[maxn], t[maxn*2];
int wall[(maxn*2) << 2];
void push(int x){
if (wall[x] <= 0) return;
wall[x<<1] = wall[x];
wall[x<<1|1] = wall[x];
}
void pull(int x){
if (wall[x<<1] != wall[x<<1|1]) wall[x] = 0;
else wall[x] = wall[x<<1];
}
void cover(int x, int L, int R){
if (wall[x] == -1) return; //seg-x 尚未張貼任何海報
if (wall[x] != 0){
//seg-x 原貼著編號"wall[x]"的海報，[L, R]區間會被新海報覆蓋
size[wall[x]] -= R - L + 1;
return;
}
// wall[x] = 0: 表示 seg-x 貼有兩種以上的海報
int mid = (L + R) >> 1;
cover(x<<1, L, mid);
cover(x<<1|1, mid+1, R);
}
void update(int x, int L, int R, int ul, int ur, int p){
if (ul <= L && R <= ur){
cover(x, L, R); //舊海報被新海報覆蓋
wall[x] = p; //seg-x 貼著一張海報，編號 p
return;
}
int mid = (L + R) >> 1;
push(x);
if (ul <= mid) update(x<<1, L, mid, ul, ur, p);
if (mid < ur) update(x<<1|1, mid+1, R, ul, ur, p);
pull(x);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> c;
while (c--){
cin >> n;
memset(wall, -1, sizeof(wall));
for (int i = 1; i <= n; i++){
cin >> l[i] >> r[i];
t[i*2-1] = l[i];
t[i*2] = r[i];
}
sort(t, t+1+n*2);
m = unique(t, t+1+n*2) - t; //去重
for (int i = 1; i <= n; i++){
//離散化
l[i] = lower_bound(t, t+m, l[i]) - t;
r[i] = lower_bound(t, t+m, r[i]) - t;
size[i] = r[i] - l[i] + 1;
update(1, 1, m, l[i], r[i], i);
}
ans = 0;
for (int i = 1; i <= n; i++){
if (size[i] > 0) ans++;
}
cout << ans << "\n";
}
}