ZOJ2301(HDU1199) Color the Ball（离散化）

题意是说，有从 1 开始递增依次编号的很多球，开始他们都是黑色的，现在依次给出 n 个操作（ai，bi，ci），每个操作都是把编号 ai 到 bi 区间内的所有球涂成 ci 表示的颜色（黑 or 白），然后经过 n 次给定的操作后，求最长的连续白色区间的左端点和右端点。
这里有个技巧，就是我们不用记录所有黑色区间的信息，黑色区间的信息只是用来更新白色区间的。需要记录的是每个白色区间的左端，右端。
也就是说，对于每个涂白操作，我们就直接把这个区间记录下来；而对于每个涂黑操作，我们看他是否会对现有的所有白色区间产生影响，如果不会，直接忽略掉，如果这个涂黑操作对现有的白色区间产生了影响（比如一个黑色区间覆盖了一个白色区间的一部分，或者一个黑色区间出现在已有的一个白色区间中间，把他分割成了俩个白色区间），那么就要调整现有的白色区间的左值、右值。

最后，遍历保存的所有白色区间，同时合并相交，或者相接的区间，找到最大值

Thanks：
[cpp]
#include<stdio.h>
#include<stdlib.h>

#define N 2010
int cnt;

struct Node{
    int left,right;
}in[N];

int cmp(const void *a,const void *b){
    struct Node *c=(Node *)a;
    struct Node *d=(Node *)b;
    return c->left - d->left;
}

void swap(int &a,int &b){
    if(a>b){
        int tmp=a; a=b; b=tmp;
    }
}

void white(int a,int b){
    in[cnt].left = a;
    in[cnt++].right = b;
}

void black(int a,int b){
    //PS ：in[N]里面保存的都是白色区间
    int i,tmp = cnt;
    for(i=0;i<tmp;i++){
        if(in[i].left < a){

            if(in[i].right >= a){
                //即将插入的黑色区间和 in[i] 区间有交集，覆盖掉了 in[i] 的一部分，并没有新增白色区间个数
                if(in[i].right <= b){
                    in[i].right = a-1;
                }
                //第 in[i] 个白色区间的右值比 b 小，也就是说即将插入的黑色区间把 in[i] 分割成了两个区间
                else {
                    in[cnt].left = b+1;
                    in[cnt++].right = in[i].right;

                    in[i].right = a-1;
                }
            }

        }
        else if(in[i].left <= b){
            //同上
            if(in[i].right <= b){// in[i] 被即将插入的黑色区间完全覆盖
                in[i].left = 0;//标志位，表示该区间是否还存在白点
                in[i].right = -1;//目测是为了方便计算区间长度而定为 -1 的
            }
            else {//覆盖了一部分，只需要修改边界即可
                in[i].left = b+1;
            }

        }
    }
}

int main()
{
    int a,b,n,i,index;
    char op[3];
    while(~scanf("%d",&n)){
        //memset(in,0,sizeof(in));
        cnt = 0;
        for(i=0;i<n;i++){
            scanf("%d%d%s",&a,&b,op);
            swap(a,b);

            if(op[0]=='w')white(a,b);
            else black(a,b);
        }

        index = 0;
        qsort(in,cnt,sizeof(in[0]),cmp);
        int max = in[0].right-in[0].left+1;
        for(i = 1;i<cnt;i++){
            if(in[i].left != 0){
                if(in[i].left <= in[i-1].right+1){
                    if(in[i-1].right <= in[i].right){//相当于相交(或相接)的两个白色区间合并
                        in[i].left = in[i-1].left;
                    }
                    else {//这里是必须的，in[i] 是为了 in[i+1] 更新的
                        in[i].left = in[i-1].left;
                        in[i].right = in[i-1].right;
                    }
                }
            }

            (in[i].right-in[i].l

补充：软件开发 , C++ ,