链接：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610
题目大意：
在一条长度为8000的线段上染色，每次把区间[a,b]染成c颜色。显然，后面染上去的颜色会覆盖掉之前的颜色。
求染完之后，每个颜色在线段上有多少个间断的区间。
注意：
因为染色的是区间，是从最左边的向右开始染色，所以更新的时候左端点可以加1。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 8005;
int n, col[maxn<<2], vis[maxn<<2], ans[maxn];
void inline push_down(int rt)
{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 mid = (left + right) >> 1;if(l <= mid)update(rt<<1, left, mid, l, r, data);if(r > mid)update(rt<<1|1, mid+1, right, 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 mid = (left+right) >> 1;query(rt<<1, left, mid);query(rt<<1|1, mid+1, right);}
}
int main()
{int u, v, w;while(scanf("%d", &n) != EOF){memset(col, -1, sizeof(col));for(int i = 1; i <= n; i++){scanf("%d%d%d", &u, &v, &w);if(u >= v)continue;update(1, 1, 8000, u+1, v, w);}memset(vis, -1, sizeof(vis));query(1, 1, 8000);memset(ans, 0, sizeof(ans));int i = 1;while(i <= 8000){int color = vis[i], j = i + 1;if(color == -1){++i;continue;}while(vis[j] == color && j <= 8000)++j;++ans[color];i = j;}for(int i = 0; i <= 8000; i++)if(ans[i])cout << i << " " << ans[i] << endl;puts("");}return 0;
}