題目大意：
在長度為10000000的牆上貼海報，海報的高度和牆的高度一樣，不同的海報覆蓋在不同的區域。如果有重疊位置，則後面貼的海報會把之前貼的海報覆蓋掉。問最終有幾張海報可以看到？
分析與總結：
又一道成段更新的線段樹染色問題來喽。
1. 用map來離散化，結果TLE了。。。然後改用數組存，用二分查詢位置，63MS過了，看來以後都不要再用map了。 www.2cto.com
2. 水過了之後，翻翻傻崽的博客，結果發現自己確實是水過的Orz...主要是離散化會產生一個問題（摘自傻崽博客）：
普通的離散化會造成許多錯誤(包括我以前的代碼,poj這題數據奇弱)
給出下面兩個簡單的例子應該能體現普通離散化的缺陷:
例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通離散化後都變成了[1,4][1,2][3,4]
線段2覆蓋了[1,2],線段3覆蓋了[3,4],那麼線段1是否被完全覆蓋掉了呢?
例子一是完全被覆蓋掉了,而例子二沒有被覆蓋
為了解決這種缺陷,我們可以在排序後的數組上加些處理,比如說[1,2,6,10]
如果相鄰數字間距大於1的話,在其中加上任意一個數字,比如加成[1,2,3,6,7,10],然後再做線段樹就好了.
代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(str,x) memset(str,(x),sizeof(str))
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
#define FF(i,n) for(int i=0; i<(n); ++i)
#define mid ((left+right)>>1)
#define len (right-left+1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
#define STOP puts("Stop Here~");
using namespace std;
const int MAXN = 40005;
int n;
int hash[MAXN<<2],seg[MAXN][2],col[MAXN<<2],vis[MAXN];
inline void push_down(int rt){
if(col[rt]==-1)return;
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
void update(int rt,int left,int right,int l,int r,int data){
if(l<=left && right<=r){
col[rt] = data;
return;
}
if(col[rt]==data) return;
push_down(rt);
int m = mid;
if(l <= m)update(lson,l,r,data);
if(r > m)update(rson,l,r,data);
}
void query(int rt,int left,int right){
if(col[rt]>=0){
vis[col[rt]]=1;
return;
}
if(left!=right && col[rt]==-1) {
int m = mid;
query(lson);
query(rson);
}
}
int binary(int left,int right,int x){
while(left < right){
int m = mid;
if(hash[m] >= x)right=mid;
else left=mid+1;
}
return left;
}
int main(){
int T,l,r;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
int pos=0;
FF(i,n){
scanf("%d%d",&l,&r);
seg[i][0]=l;
seg[i][1]=r;
hash[pos++]=l;
hash[pos++]=r;
}
sort(hash,hash+pos);
int kk=1;
FOR(i,1,pos){
if(hash[i]!=hash[i-1])
hash[kk++]=hash[i];
}
//如果相鄰數字間距大於1的話,在其中加上任意一個數字
pos = kk;
FOR(i,1,pos){
if(hash[i]-hash[i-1]>1)
hash[kk++] = hash[i-1]+1;
}
sort(hash,hash+kk);
memset(col,-1,sizeof(col));
FF(i,n) {
int a=binary(0,kk,seg[i][0]);
int b=binary(0,kk,seg[i][1]);
++a;++b;
update(1,1,kk,a,b,i);
}
int cnt=0;
mem(vis,0);
query(1,1,kk);
FF(i,kk+1){
if(vis[i]==1)++cnt;
}
printf("%d\n",cnt);
}
return 0;
}
