ZOJ1610 Count the Colors(线段树区间染色，成段更新)

题目：

Count the Colors

---

Time Limit: 2 Seconds       Memory Limit: 65536 KB

---

Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.

Your task is counting the segments of different colors you can see at last.

Input The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.

Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces: x1 x2 c x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.

All the numbers are in the range [0, 8000], and they are all integers.

Input may contain several data set, process to the end of file.

Output Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.

If some color can't be seen, you shouldn't print it.

Print a blank line after every dataset.

Sample Input 5 0 4 4 0 3 1 3 4 2 0 2 2 0 2 3 4 0 1 1 3 4 1 1 3 2 1 3 1 6 0 1 0 1 2 1 2 3 1 1 2 0 2 3 0 1 2 1

Sample Output 1 1 2 1 3 1

1 1

0 2 1 1

思路：

题目给出n个数据，有一个0~8000的区间，每组数据包含区间的左右端点和要染成的颜色，最后要输出每种颜色有几个区间。

在建树的时候要用8000来建树，还要注意一个区间问题：

比如  1 2 1

  3 4 1

这时候应该 输出1 2，所以我们在更新区间的时候要给左区间加上1.剩下的就是在询问的时候，用一个值来代表当前的颜色，只有当颜色不同时，对应的记录颜色区间个数点的数组要+1

代码：

#include <cstdio> #include <cstring> #include <cctype> #include <string> #include <set> #include <iostream> #include <stack> #include <cmath> #include <queue> #include <vector> #include <algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define N 10050x #define ll long long using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int sum[N<<2],num[N],tot; void pushdown(int rt) { if(sum[rt]!=-1) { sum[rt<<1]=sum[rt<<1|1]=sum[rt]; sum[rt]=-1; } } void update(int L,int R,int c,int l,int r,int rt) { if(L<=l&&r<=R) { sum[rt]=c; return; } pushdown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,c,lson); if(m<R) update(L,R,c,rson); } void query(int l,int r,int rt) { if(l==r) { if(sum[rt]>=0&&sum[rt]!=tot) num[sum[rt]]++; tot=sum[rt];//如果区间连续就不记录 return; } pushdown(rt); int m=(l+r)>>1; query(lson); query(rson); } int main() { int n,a,b,c; while(~scanf("%d",&n)) { mem(num,0); mem(sum,-1); tot=-1; for(int i=1; i<=n; i++) { scanf("%d%d%d",&a,&b,&c); update(a+1,b,c,1,8000,1); } query(1,8000,1); for(int i=0; i<=8000; i++) if(num[i]) printf("%d %d\n",i,num[i]); puts(""); } return 0; }