zoj1610:count the colors

Description

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

题目大意：

在一段0-8000的区间上面按题目指定区间涂色，后涂上去的颜色将覆盖前面的颜色。问最后能够看见的颜色的种类及该颜色片段数量，按从小到大的顺序输出，如片段数为0则不输。

解题思路：

可使用线段树来做。最后输出时先将线段树树组中的颜色存入一个新的数组中，将该数组遍历一遍再存入一个新数组用来存储颜色出现的片段数。

代码如下：

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
struct node
{
    int n;
}a[];
int b[];//存储颜色
int c[];//存储颜色出现的次数
int n;
void init();
void updata(int root,int ns,int ne,int us,int ue,int addval);
void pushDown(int root);
void query(int root,int l,int r);
int main()
{
    int N,i,x,y,z;
    while(cin>>n)
    {
        init();
        N=n;
        while(N--)
        {
            cin>>x>>y>>z;
            updata(,,,x+,y,z);
        }

        memset(b,-,sizeof(b));
        memset(c,,sizeof(c));

        query(,,);
        for(i=;i<=;)
        {
            while(i<=&&b[i]==-)
            i++;

            if(i>)
            break;

            int temp=b[i];
            c[temp]++;

            while(i<=&&b[i]==temp)//若颜色连续，则不计数右移
            i++;

        }
        for(i=;i<=;i++)
        {
            if(c[i]!=)
            cout<<i<<" "<<c[i]<<endl;
        }
        cout<<endl;
    }
    return ;
}
void init()
{
    int i;
    for(i=;i<=;i++)
    a[i].n=-;
}
void updata(int root,int ns,int ne,int us,int ue,int addval)
{
    if(us>ne||ue<ns)
    return;
    if(us<=ns&&ue>=ne)
    {
       a[root].n=addval;
       return;  
    }
    if(a[root].n==addval)
    return;

    pushDown(root);//延迟操作 
    int mid=(ns+ne)/;
    updata(root*,ns,mid,us,ue,addval);
    updata(root*+,mid+,ne,us,ue,addval);

}
void pushDown(int root)
{
    if(a[root].n!=-)
    {
        a[root*].n=a[root*+].n=a[root].n;
        a[root].n=-;//注意向下延迟后一定要将根节点初始化 
    }
}
void query(int root,int l,int r)
{
    if(a[root].n!=-)
    {
        for(int i=l;i<=r;i++)
        b[i]=a[root].n;

        return;
    }
    if(a[root].n==-&&l!=r)
    {
        int mid=(l+r)/;
        query(root*,l,mid);
        query(root*+,mid+,r);
    }
}