题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610
F - Count the Colors
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 11 1
0 2 1 1
思路：这道题和poj2528贴海报那道题十分像，只不过那道题是让你输出颜色的种类数，这道题是求出每个颜色有几段。
暴力建线段树，区间更新，最后查询的时候都pushdown到子节点查询就ok。
这道题有几个坑点
1.题中样例给的区间是一段，不是一个点。例如：[1，3]代表（1，2）和（2，3）两段，并不代表1，2，3三段，这一点不注意会段错误。
2.每次查询的区间应该是1~8000，而不是1~n.
最后上代码：
#include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> #define MAXN 8010 using namespace std; int a,b,c; int tree[MAXN<<2]; int ans; int tmp; int col[8010]; void pushdown(int p) { if(tree[p]!=-1) { tree[p<<1]=tree[(p<<1)|1]=tree[p]; } tree[p]=-1; } void update(int p,int l,int r,int x,int y,int a) { if(x<=l&&y>=r) { tree[p]=a; return ; } if(tree[p]!=-1) pushdown(p); int mid=(l+r)>>1; if(y<=mid) update(p<<1,l,mid,x,y,a); else if(x>mid) update((p<<1)|1,mid+1,r,x,y,a); else { update(p<<1,l,mid,x,mid,a); update((p<<1)|1,mid+1,r,mid+1,y,a); } } void query(int p,int l,int r) { if(l==r) { if(tree[p]!=-1&&tree[p]!=tmp) //因为查的是连续的段，所以和之前颜色不一样才算新的一段。 { col[tree[p]]++; } tmp=tree[p]; return ; } pushdown(p); int mid=(l+r)>>1; query(p<<1,l,mid); query((p<<1)|1,mid+1,r); } int main() { int n; while(scanf("%d",&n)!=EOF) { memset(tree,-1,sizeof(tree)); memset(col,0,sizeof(col)); for(int i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); update(1,1,8000,a+1,b,c); //左端点加1解决第一个坑点 } tmp=-1; query(1,1,8000); //查询区间为1~8000 for(int i=0;i<=8000;i++) { if(col[i]!=0) printf("%d %d\n",i,col[i]); } printf("\n"); } return 0; }