本文共 2409 字，大约阅读时间需要 8 分钟。

题目：

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

思路：

因为此题中x1,x2表示的是以x1为起点，x2为终点的区间，x1,x2表示的是点，而不是线段，所以我们不能直接构造线段树，我们可以将x1+1,或者x2-1，这样就可以使点变成线段了，因为范围减小了1，我当时做的时候是x2-1,结果越界了。然后就用的x1+1。

利用区间更新来覆盖颜色。

然后通过区间查询寻找答案，这里的区间查询比较特殊，是将所有线段的颜色都记录下来，然后看看有多少连续的线段。

如果只是看到一段区间有颜色就记录下来的话，会使几段可以连成一段连续线段分别记录，就使 结果变大。

代码如下：

 

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=8*1e3+5;int n;int tree[maxn<<2];int ans[maxn<<2];int col[maxn<<2];void push_down(int rt){    if(tree[rt]!=-1)    {        tree[rt<<1]=tree[rt<<1|1]=tree[rt];        tree[rt]=-1;    }}void update (int L,int R,int x,int l,int r,int rt){    if(l>=L&&r<=R)    {        tree[rt]=x;        return;    }    int m=(l+r)>>1;    push_down(rt);    if(L<=m) update (L,R,x,l,m,rt<<1);    if(R>m) update (L,R,x,m+1,r,rt<<1|1);}void query (int l,int r,int rt){    if(tree[rt]!=-1)    {        for (int i=l;i<=r;i++)        {            col[i]=tree[rt];        }        return;    }    if(l==r) return;    int m=(l+r)>>1;    push_down(rt);    query(l,m,rt<<1);    query(m+1,r,rt<<1|1);}int main(){    while(scanf("%d",&n)!=EOF)    {        memset (col,-1,sizeof(col));        memset (ans,0,sizeof(ans));        memset (tree,-1,sizeof(tree));        while(n--)        {            int x,y,c;            scanf("%d%d%d",&x,&y,&c);            if(x
      
     
    
   

 

转载地址：http://hzoen.baihongyu.com/