ZOJ 1610 Count the Colors(線分カバーの着色:離散化)

ZOJ 1610 Count the Colors(線分カバーの着色:離散化)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610
件名:
       n条の[0,8000]の範囲内の異なる色の線分をあげます.最後にこの線分にはどの色がありますか?そしてこれらの色はそれぞれ何回現れましたか?
分析:
       本題は線分樹でできますが、離散化はもっと簡単で分かりやすいです.そして本題は前に作ったZOJ 2747と本質的に同じです.
http://blog.csdn.net/u013480600/article/details/39479819
       まず、各セグメントを読み込んで、すべての異なるx座標を保存して、x座標を並べ替えて重さを取ります.その後のx配列サイズ-1は有効区間全体を線分でいくつのサブセグメントに分けましたか?各サブセグメントの色は最後の線分に着色された元の線分だけです.
       その後、私たちは各サブセグメントをスキャンすれば、各色に何回ずつ現れたかを記録できます.
       いくつかのサブセグメントが連続して同じ色になったら、この色は1回しか出ないということです.
ACコード:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=8000*2+5;

int n;      //      
int x[maxn];//   x  
int num1;   //x    
struct Node
{
    int x1,x2,c;
}nodes[maxn];

int main()
{
    while(scanf("%d",&n)==1)
    {
        num1=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d%d%d",&nodes[i].x1,&nodes[i].x2,&nodes[i].c);
            x[num1++]=nodes[i].x1;
            x[num1++]=nodes[i].x2;
        }
        sort(x,x+num1);
        num1=unique(x,x+num1)-x;

        int color[maxn];//color[i]  x[i] x[i+1]     
        for(int i=0;i<num1;++i) color[i]=-1;//   ,-1     

        for(int i=0;i<n;++i)
        {
            int L_x=lower_bound(x,x+num1,nodes[i].x1)-x;
            int R_x=lower_bound(x,x+num1,nodes[i].x2)-x;

            for(int j=L_x;j<R_x;++j) color[j]=nodes[i].c;//  
        }

        int ans[maxn];//ans[i]==x  i      x 
        memset(ans,0,sizeof(ans));
        for(int i=0;i<num1;++i)
        {
            if(color[i]>=0&&color[i]!=color[i+1]) ++ans[color[i]];
        }

        for(int i=0;i<=8000;++i)if(ans[i])
            printf("%d %d
",i,ans[i]);
        printf("
");
    }
    return 0;
}