学步园

题意是说，有从 1 开始递增依次编号的很多球，开始他们都是黑色的，现在依次给出 n 个操作（ai，bi，ci），每个操作都是把编号 ai 到 bi 区间内的所有球涂成 ci 表示的颜色（黑 or 白），然后经过 n 次给定的操作后，求最长的连续白色区间的左端点和右端点。

这里有个技巧，就是我们不用记录所有黑色区间的信息，黑色区间的信息只是用来更新白色区间的。需要记录的是每个白色区间的左端，右端。

也就是说，对于每个涂白操作，我们就直接把这个区间记录下来；而对于每个涂黑操作，我们看他是否会对现有的所有白色区间产生影响，如果不会，直接忽略掉，如果这个涂黑操作对现有的白色区间产生了影响（比如一个黑色区间覆盖了一个白色区间的一部分，或者一个黑色区间出现在已有的一个白色区间中间，把他分割成了俩个白色区间），那么就要调整现有的白色区间的左值、右值。

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

Thanks：http://blog.csdn.net/zdsfwy/article/details/6299444

#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].left+1 > max) ? (max = in[i].right-in[i].left+1 , index=i) : max;
		}
		max == 0 ? puts("Oh, my god") : printf("%d %d\n",in[index].left,in[index].right);
	}
	return 0;
}