題目鏈接：[點擊打開鏈接](http://poj.org/problem?id=2528) 題意：在墻上貼海報,海報可以互相覆蓋,問最后可以看見幾張海報。 該題是線段樹區間修改+離散化的應用。 不難想到， 每次對一個最長10^7的線段進行線段樹的區間修改， 最后統計。 線段樹的復雜度是log10^7， 應該不會超時， 但是會超內存。 所以想到要離散化， 將區間端點值有映射成一個盡量小的值。 但是該題求的是覆蓋情況， 如果按照單純的點對點的離散化， 那樣會出現錯誤答案。 例如： ?依次貼[1,10], [1,3], [5,10] ， 離散化后1->1, 3->2, 5->3, 10->4 那么第一次讓離散后的區間[1,4]變成1，第二次讓[1,2]變成2，第三次讓[3,4]變成3，那么最終答案成了2， 其實是3。 問題之所在就在于：小的區間不會覆蓋大區間的所有部分。 解決方法就是在相鄰區間端點大于1時再添加一個二者中間的數當作“空白”區域。 不會離散化的先學學離散化吧， 一般用二分來維護比較簡單。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 11111; int T,n,ans,setv[maxn<<4],X[maxn<<3]; bool vis[maxn]; struct node { int l, r; node(int ll=0, int rr=0):l(ll), r(rr) {} bool operator < (const node& rhs) const { return l < rhs.l || (l == rhs.l && r < rhs.r); } }a[maxn]; void pushdown(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) { int m = (l + r) >> 1; if(L <= l && r <= R) { setv[o] = v; return ; } pushdown(o); 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) { int m = (l + r) >> 1; if(setv[o]) { if(!vis[setv[o]]) { vis[setv[o]] = true; ++ans; } return ; } if(l == r) return ; query(l, m, o<<1); query(m+1, r, o<<1|1); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); int cnt = 0; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); X[cnt++] = a[i].l; X[cnt++] = a[i].r; } sort(X, X+cnt); cnt = unique(X, X+cnt) - X; int m = cnt; for(int i=1;i<cnt;i++) { if(X[i] > X[i-1]+1) X[m++] = X[i] + 1; } sort(X, X + m); memset(vis, false, (n+1)*sizeof(vis[0])); memset(setv, 0, sizeof(setv)); for(int i=1;i<=n;i++) { int lc = lower_bound(X, X + m, a[i].l) - X + 1; int rc = lower_bound(X, X + m, a[i].r) - X + 1; update(lc, rc, i, 1, m, 1); } ans = 0; query(1, m, 1); printf("%d\n",ans); } return 0; } ~~~