hdu1199 Color the Ball (简单离散化)

题目：

题目大意，是说对一串小球进行染色，小球的编号为1，2。。。，初始时，所有的小球为黑色，然后就给出N次染色，每次染色是对编号a和编号b之间的球全部染成white或black，最后要求出最长的white，给出其起点和终点球的编号。。如果没有white，则输出"Oh,my god".这题本来听说是用线段树写的，但想了半天，依旧想不出来。惭愧啊。最后直接模拟，居然不超时。。很神奇。。。

   大致思路：对于染成白色的操作，记录下此白色线段。。对于染成黑色的操作，分四种情况。。所有操作完成后，对白色线段按起始位置从小到大排序。再顺序遍历下白色线段，记录下最长的白色线段的起始和结束位置。。其中有些白线段的合并等处理，类似于上次的pku3642 Lucky Light(见以前的博文)。。

my code:

 

#include<iostream>
using namespace std;

struct Line
{
    int start;
    int end;
};

int cmp(const void *a,const void *b)
{
    return ((Line *)a)->start>((Line *)b)->start?1:-1;
}
int main()
{
    int N,i,len,temp;
    int a,b,tempsize,maxsize,tstart,tend,ansstart,ansend;
    char ch;
    Line line[20000];
    while(cin>>N)
    {
        len=0;
        while(N--)
        {
            cin>>a>>b>>ch;
            if(a>b){a^=b;b^=a;a^=b;}
            if(ch=='w')
            {
                line[len].start=a;
                line[len].end=b;
                len++;
            }
            else
            {
                temp=len;
                for(i=0;i<temp;i++)//分4种情况
                {
                    if(a<=line[i].start&&b>=line[i].start&&b<line[i].end){line[i].start=b+1;continue;}
                    if(a>line[i].start&&a<=line[i].end&&b>=line[i].end){line[i].end=a-1;continue;}
                    if(a>line[i].start&&b<line[i].end)
                    {
                        line[len].start=b+1;
                        line[len].end=line[i].end;
                        line[i].end=a-1;
                        len++;
                        continue;
                    }
                    if(a<=line[i].start&&b>=line[i].end)
                    {
                        line[i].start=-1;
                        line[i].end=-1;
                    }
                }
            }
        }
        qsort(line,len,sizeof(Line),cmp);
        tstart=-1;tend=-2;maxsize=0;
        for(i=0;i<len;i++)//对白线段进行处理
        {
            if(line[i].start!=-1)
            {
                if(line[i].start>tend+1)
                {
                    tempsize=tend-tstart+1;
                    if(tempsize>maxsize)
                    {
                        maxsize=tempsize;
                        ansstart=tstart;
                        ansend=tend;
                    }
                    tstart=line[i].start;
                    tend=line[i].end;
                }
                else
                    tend=tend>line[i].end?tend:line[i].end;
            }
        }
        tempsize=tend-tstart+1;
        if(tempsize>maxsize)
        {
            maxsize=tempsize;
            ansstart=tstart;
            ansend=tend;
        }
        if(maxsize==0) cout<<"Oh, my god"<<endl;
        else cout<<ansstart<<" "<<ansend<<endl;
    }
    return 0;
}