HDU 1199（Color the Ball）

题目分析：在一个很长的节点序列上（长度最大可以到2^31）,如果建树，则离散不了各个节点，因为求的是长度区间，在次我们换向考虑一下，原始是黑色的 各个节点，我们只需考虑对白色节点进行染黑的操作，其他的都不需要考虑，把各个连续的白色节点区间存储在节点数组里面，然后当遇到要进行染黑操作时，直接在白色区间数组里分个进行讨论，没个区间枚举四种不同情况，相应的维护区间。

最后就是在计算最长去区间 的时候稍微要点技巧：1）首先考虑前后是否可以合并，2）保存目前最大值，与最大值的区间端点。

代码如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;

struct node{
	int beg,en;
}s[8000];

int cmp(struct node a,struct node b){
	if(a.beg!=b.beg){
		return a.beg<b.beg;
	}
	else 
		return a.en>b.en;
}

int main(){
	int n,beg,en,sn,tn;
	int Max,x,y,len,i;
	char c;
	while(scanf("%d",&n)!=EOF){
		memset(s,0,sizeof(s));//每次个案例都要初始化哦，请您注意一下
		len=0;
		while(n--){
			scanf("%d %d %c",&beg,&en,&c);
			if(c=='w'){
				s[len].beg=beg;
				s[len].en=en;
				len++;			
			}
			else{
				for(i=0;i<len;i++){
					if(beg<=s[i].beg&&en>=s[i].en)
						s[i].beg=s[i].en=-1;
					else if(beg<=s[i].beg&&en<=s[i].en&&en>=s[i].beg)
						s[i].beg=en+1;
					else if(beg>=s[i].beg&&en<=s[i].en){
						s[len].en=s[i].en;
						s[i].en=beg-1;
						s[len].beg=en+1;
						len++;
					}
					else if(beg>=s[i].beg&&en>=s[i].en&&beg<=s[i].en)
						s[i].en=beg-1;
				}
			}
		}
		Max=x=y=-1;
		sort(s,s+len,cmp);
		//for(i=0;i<len;i++)
			//cout<<s[i].beg<<" "<<s[i].en<<endl;
		for(i=0;i<len;i++){
			if(s[i].beg!=-1){
				if(s[i].beg<=y+1)
					y=max(s[i].en,y);
				else {
					x=s[i].beg;	y=s[i].en;				
				}
				if(Max<y-x+1){
					Max=y-x+1;
					sn=x;	tn=y;		
				}
			}
		}
		if(Max==-1)
			printf("Oh, my god\n");
        	else
            		printf("%d %d\n",sn,tn);
	}
	return 0;
}