題目大意：
在一條長度為8000的線段上染色，每次把區間[a,b]染成c顏色。顯然，後面染上去的顏色會覆蓋掉之前的顏色。
求染完之後，每個顏色在線段上有多少個間斷的區間。
分析與總結：
這題是成段更新lazy標記的題，並不算難，但是因為一些原因一直讓我過不去。。。
1. 昨天做了這題，但是一直連樣例都出不來 = =～！早上起來，突然醒悟發現了問題所在，題目每次給的染色段是把[a,b]染成c，之前一直以為就是把a～b的所有點都染成c， 其實不是這樣的，要染色的不是點，而是區間，例如要染[0,1]，並不是把0，1兩點染色，而是把[0,1]這一個單位區間進行染色。 假設有一個樣例：
1 2 1
3 4 1
那麼這個樣例應該輸出1 2. 只需要在紙上畫一下就可以發現，區間【2，3】是沒有被染色的，所以有兩個間斷的區間顏色是1。
解決這個問題的辦法是，建立線段樹build(1,1,8000)，代表區間1～8000， 然後更新時是update(1,1,8000, a+1,b,c);
2. 由於沒有仔細看題目，看錯了一個地方，於是一直RE（在zoj上叫做Segmentation Fault）：
The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.
這句話的意思是只有n條線段被染色，而我一直理解成了是在一條n個單位區間長度的線段上染色 = =～ 於是就悲劇了。
正解是這句話：All the numbers are in the range [0, 8000], and they are all integers.
代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring> www.2cto.com
#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 = 8005;
int n,col[MAXN<<2],vis[MAXN<<2],ans[MAXN<<2];
inline void push_down(int rt){
if(col[rt] != -1){
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;
if(col[rt]!=-1)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){
for(int i=left; i<=right; ++i)
vis[i] = col[rt];
return;
}
if(left!=right && col[rt] == -1){
int m = mid;
query(lson);
query(rson);
}
}
int main(){
int a,b,c;
while(~scanf("%d",&n)){
memset(col,-1,sizeof(col));
for(int i=0; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
if(a>=b)continue;
update(1,1,8000,a+1,b,c);
}
mem(vis,-1);
query(1,1,8000);
int i = 1;
mem(ans,0);
while(i<MAXN){
int color=vis[i], j=i+1;
if(color==-1){++i; continue;}
while(vis[j]!=-1 && vis[j]==color && j<MAXN) ++j;
++ans[color];
i=j;
}
for(int i=0; i<MAXN; ++i)if(ans[i])
printf("%d %d\n",i,ans[i]);
puts("");
}
return 0;
}
