题目大意：给出对角线让您求所有矩形构成整体的并周长。

解题分析：这里跟求面积所要求的基本操作是一致的。对Y进行离散化，然后建树，树节点里比起求并面积的多了几个域，一个是记录左右端点被覆盖的次数lb,rb，一个是记录区间内连续子段的个数。

通过上面的记录更新我们可以这样计算：

1）通过Y的长度就是，把这次在Y轴上的投影与上次的取差的绝对值，这就是它在Y上面的增量，把这些增量求和，这样就解决了Y上的周长问题！

2）因为线段树的节点里已经计算出目前该区间的连续子区间的个数，所以在这里就可以计算周长在X上的长度，因为Y上的段树就表明有该区间X的元线段要计算多少次，计算公式：sum+=2*(t[i].x-t[i-1].x)*lastn;在这里lastn表示上一次计算出的Y上投影的区间个数，也就是我这次计算所涉及的！

代码程序如下：

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

int ym[10200];//注意区间要开大点 不然RE

struct Tree{
	int li,ri,lb,rb;//li,ri左右端点的值
	int lenth,ans,cover;//lenth表示被覆盖至少一次的长度
       //ans记录子区间个数,lb,rb记录左右端点被覆盖次数
       //cover记录整个区间被覆盖的次数
}s[50000];

struct node{
	int x,y1,y2;
	int flag;
}t[50000];//表示左，右边的节点

int cmp1(int x,int y){
	return x<y;
}

int cmp2(struct node st,struct node sd){
	if(st.x!=sd.x)
		return st.x<sd.x;
	else 
		return st.flag>sd.flag;
            //这里要非常注意，因为要计算并周长，
          //当两个边x一样的时候，要将左边先插入！
}

int len(int num){
	if(s[num].cover>0)
		s[num].lenth=s[num].ri-s[num].li;
	else
		s[num].lenth=s[num+num].lenth+s[num+num+1].lenth;
}

int slen(int num){
	if(s[num].cover>0)
		s[num].ans=1;
	else {
		s[num].ans=s[num+num].ans+s[num+num+1].ans;
		if(s[num+num].rb!=0&&s[num+num+1].lb!=0)
			s[num].ans--;	
             //左子树的右端点如果跟右子树的左端点都被覆盖了
            //说明在整个区间里，有一个区间横跨左右子树，
           //但被重复计算了，所以要减去1！
	}
}

int Build(int x,int y,int num){
	s[num].li=ym[x];	s[num].ri=ym[y];
	s[num].lenth=0;
	s[num].cover=s[num].rb=s[num].lb=s[num].ans=0;
	if(x+1==y)
		return 0;
	int mid=(x+y)>>1;
	Build(x,mid,num+num);
	Build(mid,y,num+num+1);
}

int modify(int num,struct node st){
	if(st.y1==s[num].li)	s[num].lb+=st.flag;
	if(st.y2==s[num].ri)	s[num].rb+=st.flag;
	if(st.y1==s[num].li&&st.y2==s[num].ri){
		s[num].cover+=st.flag;
	}
	else{
		if(st.y1>=s[num+num].ri)
			modify(num+num+1,st);
		else if(st.y2<=s[num+num+1].li)
			modify(num+num,st);
		else{
			struct node sd=st;
			sd.y2=s[num+num].ri;
			modify(num+num,sd);
			sd=st;
			sd.y1=s[num+num+1].li;
			modify(num+num+1,sd);
		}
	}
	len(num);
	slen(num);
}

int main(){
	int cas,i,j;
	int x1,x2,y1,y2;
	int sum=0;
	while(scanf("%d",&cas)!=EOF){
		sum=0;
		for(j=1,i=1;i<=cas;i++,j+=2){
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			ym[j]=y1;
			t[j].x=x1;
			t[j].y1=y1;
			t[j].y2=y2;
			t[j].flag=1;
			ym[j+1]=y2;
			t[j+1].x=x2;
			t[j+1].y1=y1;
			t[j+1].y2=y2;
			t[j+1].flag=-1;
		
		}
		sort(ym+1,ym+j,cmp1);
		sort(t+1,t+j,cmp2);
		Build(1,j-1,1);
		int lastn=0,lasts=0;
              //lasts 表示上次Y上次的投影长度，lastn
              //表示Y上次的投影连续区间的个数
              //其实连续区间就是指图形从上到下有多少个不相连的部分
              //因为求周长，所以有多少个部分就要把X的区间长度
              //乘以这个区间个数，因为他们每个部分的上下边不重叠
		for(i=1;i<j;i++){
			modify(1,t[i]);
			sum+=abs(lasts-s[1].lenth);
			if(i!=1){
				sum+=lastn*(t[i].x-t[i-1].x)*2;
			}
			lastn=s[1].ans;
               //当初我答案一直错，检查了很久，最后终于发现是
              //把lastn=s[1].ans；放在了if语句里面，这样的话影响了第2次的计算。所以周长计算出来会有点偏小，因为我第二次的lastn还是=0，应该是等于1，呵呵
			lasts=s[1].lenth;
		
		}
		printf("%d\n",sum);
	}
}

题目大意：给对角线 求覆盖次数至少为2次的面积

思路：首先把Y离散化，从小到大排序，然后以Y在数组种存放的位置，建树。但是线段树的lf,rf,存放的是Y的实际值，这就是离散化。

然后 在节点里用cover记录被覆盖的次数，lenth表示至少被覆盖一次的区间长度,inlenths,记录被覆盖两次以上的区间长度，这里比起求矩形的并面积，就是多了个记录与更新至少覆盖两次的情况的操作！
建树：跟求区间的并 区别不大，就是多了一个对inlenths的初始化。

更新：从上到下遍历，找到需要更新区间，如果是矩形的左边，cover加1，表示在这个高度，多了个区间覆盖在其之上，如果是矩形的右边则减1，说明，少了个区间覆盖在这个高度范围内，也就是矩形的覆盖，更新当前区间的lenth,如果cover>0则lenth等于该区间的整体长度，否则等于左右子树的覆盖长度，然后更新inlenths的长度，当cover>2,表明这个高度有2个以上矩形覆盖，即把inlenths赋值为当前区间的整体长度，如果cover=1说明这个区间整体只被覆盖一次，那么inlenths的值就等于左右子区间被覆盖一次以上的长度，因为整体的已经被覆盖了一次，只有子区间有被覆盖过大于等于一次，那么该长度也被覆盖了2次以上！，最后当cover=0，那么说明这个区间没有整体被覆盖过，那么inlenths等于左右子区间的inlenths的长度！最后结束这次的遍历。如果没有到达更新区间，那么就分三种情况，在左子树，右子树，左右子树混合的情况，分别考虑，然后每次都会往上更新lenth和inlenths的值！

源程序代码+部分注释：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define esp (1e-8)
using namespace std;
double x_1,y_1,x_2,y_2,ym[30000],sum;
int i,j,n,cas;
struct tree{
	double lf,rf,lenth,inlenths;
	int cover;
}s[80000];
//这里数组开的小了当初，WA了好多次
//所以一气之下开的很大！
struct node{
	double x,y1,y2;
	int flag;
}t[30000];

void len(int num){
	if(s[num].cover>0)
		s[num].lenth=s[num].rf-s[num].lf;
	else
		s[num].lenth=s[num+num].lenth+s[num+num+1].lenth;
}

void inlen(int num){
	if(s[num].cover>1)//表示整个区间被覆盖次数大于等于2
		s[num].inlenths=s[num].rf-s[num].lf;
	else if(s[num].cover==1)
		s[num].inlenths=s[num+num].lenth+s[num+num+1].lenth;
                //整个区间只被覆盖一次，如果子区间有被覆盖大于等于1次，说明该子段的长度，
                //为被覆盖至少2次的长度
	else
		s[num].inlenths=s[num+num].inlenths+s[num+num+1].inlenths;
                //整个区间都没被覆盖，该区间覆盖2次以上的长度就等于
                //他左右子树被覆盖的长度的和
}

int cmp1(double a,double b){
	return a<b;
}

int cmp2(struct node a,struct node b){
	return a.x<b.x;
}

int Build(int x,int y,int num){
	s[num].lf=ym[x];
	s[num].rf=ym[y];
	s[num].cover=s[num].lenth=s[num].inlenths=0;
	if(x+1==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid,y,num+num+1);
}

int modify(int num,struct node n){
	if(fabs(s[num].lf-n.y1)<=esp&&fabs(s[num].rf-n.y2)<=esp){
		s[num].cover+=n.flag;
		len(num);
		inlen(num);
		return 0;
	}
        //以下是分三种情况进行讨论
	if(n.y1>=s[num+num].rf)
		modify(num+num+1,n);
	else if(n.y2<=s[num+num+1].lf)
		modify(num+num,n);
	else{
		struct node sn=n;
		sn.y2=s[num+num].rf;
		modify(num+num,sn);
		sn=n;
		sn.y1=s[num+num+1].lf;
		modify(num+num+1,sn);
	}
	len(num);
	inlen(num);
}

int main(){
	scanf("%d",&cas);
	while(cas--){	
		sum=0;
		scanf("%d",&n);
		for(i=1,j=1;i<=n;i++,j+=2){
			scanf("%lf %lf %lf %lf", &x_1, &y_1, &x_2, &y_2);
			ym[j]=y_1;
			t[j].x=x_1;
			t[j].y1=y_1;
			t[j].y2=y_2;
			t[j].flag=1;
			ym[j+1]=y_2;
			t[j+1].x=x_2;
			t[j+1].y1=y_1;
			t[j+1].y2=y_2;
			t[j+1].flag=-1;
		}
		sort(ym+1,ym+j,cmp1);
		sort(t+1,t+j,cmp2);
		Build(1,j-1,1);
		modify(1,t[1]);
		for(i=2;i<j;i++){
			sum+=s[1].inlenths*(t[i].x-t[i-1].x);
			modify(1,t[i]);
		}
		printf("%.2lf\n",sum);
              //在我的编译器上好像样例的答案为7.62但是可以过
              //我不知道有没有更好的办法能够四舍五入保留两位小数
	}
	return 0;

题目大意：给定每个矩形的对角线的两个端点，让你求这些矩形的面积的并集，即重叠的不能重复计算！

题目分析：这题就是典型的线段树求面积并！

离散化：对所有节点的Y进行升序排序，然后以Y的位置建树，就是指，在线段树里面，左右节点的实际意义就是指这个线段在Y的升序数组里的位置，但是我们把lf,rf赋值为这个线段左右端点的具体值！这就是离散化！

建树的细节：树的每个节点有lf,rf,cover,lenth，分别指这个节点所表示的线段的左端点，右端点，被覆盖的次数（在这里覆盖的次数是为了 区分重叠矩形的情况下，高度的正确存取，因为一个矩形对Y轴的覆盖是以他的左边开始，右边结束的，所以当插入左边的时候，我们把cover+1，右边的时候把cover-1，说明这个矩形对Y的覆盖已经结束，计算下一个矩形时，不会错误的把我这个矩形的高度当作下一个矩形的高度！），lenth指这个区间被矩形覆盖的长度即矩形的实际高度！；

插入的时候，先把存放节点的数组，对X进行升序排序！然后顺次插入，分别计算！

代码如下+部分注释：

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

struct tree{
	double lf,rf,lenth;
	int cover;
}s[4000];//树节点定义

double x1,y1,x2,y2,ym[1000];

struct node{
	double x,y1,y2;
	int flag;
}t[4000];//存放矩形左，右边的节点

int cmp1(double x,double y){
	return x<y;
}

int cmp2(struct node a,struct node b){
	return a.x<b.x;
}

void len(int n){
	if(s[n].cover>0)
		s[n].lenth=s[n].rf-s[n].lf;
	else
		s[n].lenth=s[2*n+1].lenth+s[2*n].lenth;
}

int Build(int x,int y,int num){
	s[num].lf=ym[x];
	s[num].rf=ym[y];
	s[num].lenth=s[num].cover=0;
	if(x+1==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid,y,num+num+1);
}

int modify(int num,struct node n){
	if(s[num].lf==n.y1&&s[num].rf==n.y2){
		s[num].cover+=n.flag;
		len(num);
		return 0;
	}
	if(n.y1>=s[num+num].rf)
		modify(num+num+1,n);
	else if(n.y2<=s[num+num+1].lf)
		modify(num+num,n);
	else{
		struct node vs=n;
		vs.y2=s[num+num].rf;
		modify(num+num,vs);
		vs=n;
		vs.y1=s[num+num+1].lf;
		modify(num+num+1,vs);
	}
	len(num);//往上更新线段被覆盖的实际长度！如果节点的cover>0 该区间节点的被覆盖就是，区间的整体程度，否则，该区间节点的被覆盖等于左右节点被覆盖长度的和！
}

int main(){
	int cas,i,j,k=1;
	double sum;
	while(cin>>cas,cas){
		for(j=i=1;i<=cas;i++,j+=2){
			scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
			ym[j]=y1;
			t[j].x=x1;
			t[j].y1=y1;
			t[j].y2=y2;
			t[j].flag=1;
			ym[j+1]=y2;
			t[j+1].x=x2;
			t[j+1].y1=y1;
			t[j+1].y2=y2;
			t[j+1].flag=-1;
		}
		sort(ym+1,ym+j,cmp1);
		sort(t+1,t+j,cmp2);
		Build(1,j-1,1);
		modify(1,t[1]);
		sum=0;
		for(i=2;i<j;i++){
			sum+=(t[i].xt[i-1].x)*s[1].lenth;
                      //每插入完一个点，就以他后继的点求面积！
			modify(1,t[i]);
		}
		printf("Test case #%d\n",k);
		printf("Total explored area: %.2lf\n\n",sum);
		k++;
	}
	return 0;
}

题意就是有两个检查站，可以从第一个检查站开进车子，也会从后面一个检查站开出车子，但是每次只能动作一次，开出或者开进，你要求查询这两个检查站之间的最重车辆。

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

struct node{
	int val,id;
};

int main(){
	int cas,x,sn,ans,t,times,en;
	char c[10];
	scanf("%d",&cas);
	list <node> que;
	node tempt ;
	en=sn=0;
	ans=0;
	times=0;
	while(cas--){
		scanf("%s",c);
                 //这样能节约很多时间！下次进行类似的字符输入
                 //用来判断的时候 切记 ！ 
            	if(c=='Q'){
			if(que.empty())
				printf("0\n");
                        else
				printf("%d\n",que.front().val);
                }
		else if(c=='I'){
			scanf("%d",&x);
			ans++;
			tempt.val=x;
			tempt.id=ans;
			while(!que.empty()&&x>=que.back().val) 
				que.pop_back();
			que.push_back(tempt);
		}
		else{	
			times++;
			while(!que.empty()&&que.front().id<=times)
				que.erase(que.begin());
		}
	}
	return 0;
}

题目分析：简单的后缀表达式，把每个表达式存放在string 变量里，然后从前到后遍历一边，当遇到'('直接存放在记录运算符的栈里，如果是 字母就把这个字母对应的 节点存放在，记录运算节点的栈里！最后当遇到 ')' 如果记录运算符号的栈里为空，就说明 括号不对称！所以得出error！否则把栈里的'('的出栈！然后把记录运算节点的栈里取出两个运算节点！对这两个节点进行判断,是否满足矩阵运算规则，如果不满足，判错！满足的话记录下他们的乘积！并且 将两个节点合并成一个节点 存放回 在记录运算节点的栈里！

算法详细过程 就是这样 下面是我的代码 如有改正的地方请您留言 谢谢

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

struct node{
	int x,y;
}s[30];
int n;
void input(){
	char c;
	while(n--){
		cin>>c;
		int t=c-'A';
		cin>>s[t].x>>s[t].y;
	}
}

int cal(string str){
	int i,k=str.length(),ans=0;
	struct node a,b;
	stack<char>sn;
	stack<struct node>st;
	for(i=0;i<k;i++){
		if(str[i]=='(')
			sn.push(str[i]);	
		else if(str[i]>='A'&&str[i]<='Z')
			st.push(s[str[i]-'A']);
		else{
			if(sn.empty())
				return -1;
			sn.pop();
			b=st.top();
			st.pop();
			a=st.top();
			st.pop();
			if(a.y!=b.x)
				return -1;
			ans+=a.x*b.x*b.y;
			a.y=b.y;
			st.push(a);
			
		}
			
	}
	return ans;
}

int main(){
	int sum;
	string str;
	cin>>n;
	input();
	while(cin>>str){
		sum=cal(str);
		if(sum==-1)
			printf("error\n");
		else
			printf("%d\n",sum);
	}
	return 0;
}

题目分析：就是让你求一个坐标数组里，满足x,y同时递增的序列个数！

              拿到题目我就想到贪心，但是一直没得到很好的证明，所以一直迟迟不敢去尝试，毕竟也是比赛，呵呵，后来有人说贪心过， 突然觉得自己也许会考虑的复杂了！其实题目也没有什么最优解选择方案，只是简简单单的 x,y同时递增的序列个数。

现在就贴一下我的代码 如果您有对本题有更好的思路希望您能给我批阅！{^_^}

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

struct node{
	int x,y;
}s[10000];

int vs[10000];

int cmp(struct node a,struct node b){
	if(a.x!=b.x)
		return a.x<b.x;
	else
		return a.y<b.y;
}

int main(){
	int cas,n,i,ans,j,t;
	cin>>cas;
	while(cas--){
		cin>>n;
		memset(vs,0,sizeof(vs));
		ans=0;
		for(i=1;i<=n;i++){
			cin>>s[i].x>>s[i].y;
		}
		sort(s+1,s+n+1,cmp);
		for(i=1;i<=n;i++){
			if(!vs[i]){
				t=s[i].y;
				ans++;
				for(j=i+1;j<=n;j++){
					if(s[j].y>=t&&vs[j]==0){
						t=s[j].y;
						vs[j]=1;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

题目大意：给出N个海报的左右边界，然后按顺序贴完这些海报，要求计算没有完全被覆盖的海报的张数。

题目分析：首先离散化：按顺序用数组把左右边界存起来，然后升序排序，去除重复出现的，最后用左右边界在该数组出现的位置作为左右边界的值；还有一个就是，计算的时候可以当作一个染色过程，倒着染，您可以自己想想一下，这样才能够使得结果不被后面的染色操作干扰，不是么！因为后面计算的都是先贴的，根本不会对我产生影响的！

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define MAX 10005 
using namespace std;

struct node{
	int a,b,color,flag;
}s[8*MAX];

struct st{
	int x,y;
}t[2*MAX];

int N[2*MAX],vs[2*MAX],sim[4*MAX],times,ans;

int cmp(int a,int b){
	return a<b;
}

int getidex(int y){
	int i=1,j=times+1,mid;
	while(i<=j){
		mid=(i+j)/2;
		if(N[mid]==y)	return mid;
		if(N[mid]>y)	j=mid;
		else i=mid+1;
	}
	return 0;
}

int Build(int x,int y,int num){
	s[num].color=0;
	s[num].flag=0;
	s[num].a=x;	
	s[num].b=y;
	if(x==y)
		return 0;
	int mid=(x+y)/2;
		Build(x,mid,num+num);
		Build(mid+1,y,num+num+1);
}

int modify(int x,int y,int num,int color){
	if(s[num].color>0) //说这个区间会被覆盖，不用再讨论了！
		return 0;
	if(x==s[num].a&&y==s[num].b){//找到查询区间
		if(s[num].flag==0){//判断是否被完全覆盖
			s[num].color=color;
			s[num].flag=1;//染色
			if(!vs[color]){//如果这个颜色没有出现过，计数！
                               //先前我这里忘记考虑了，其实这个也许是这次查询的一个子区间
                              //这里是对其中一个子区间进行染色，计数，当然，其他的子区间肯定也染色！
                              //但是计数只需要一次！！
				ans++;
				vs[color]=1;
			}
		}
		return 0;
	}
	int mid=(s[num].a+s[num].b)/2;
	if(y<=mid)
		modify(x,y,num+num,color);
	else if(x>mid)
		modify(x,y,num+num+1,color);
	else{
		modify(x,mid,num+num,color);
		modify(mid+1,y,num+num+1,color);
	}
        //重点注意一下这里：如果左右子树都被染色了
        //很显然要往上更新父亲节点的染色状态即flag!
	if(s[num+num].flag&&s[num+num+1].flag)
		s[num].flag=1;
}

int main(){
	int cas,n,i,j;
	scanf("%d",&cas);
	while(cas--){
		memset(vs,0,sizeof(vs));
		ans=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d%d",&t[i].x,&t[i].y);
                //把左右边界的存放在sim[]里面一边，以便下面的离散操作！
		for(i=1;i<=n;i++){
			sim[i]=t[i].x;
		}
		for(i=n+1,j=1;j<=n;j++,i++){
			sim[i]=t[j].y;
		}
		sort(sim+1,sim+1+2*n,cmp);//升序排序
                //去除重复的边界值
		N[1]=sim[1];
		times=1;
		for(i=2;i<=2*n;i++){
			if(N[times]!=sim[i])
				N[++times]=sim[i];
		}
		Build(1,times,1);
		int color=0;
		for(i=n;i>=1;i--){
			int sx=getidex(t[i].x);
                 //以边界值在sim[]里面的位置，作为当前的边界值，这就是离散的核心思想！
			int sy=getidex(t[i].y);
			modify(sx,sy,1,++color);
		}
		printf("%d\n",ans);
	}
	return 0;
}

题目大意：就是一个man从 最高处的横木往下跳，在这里与我们平时的游戏有点出入，在此处 我们只能往最近的，并且包含我左或右端点的一个横木区间上跳。man的初始血量为100，每跳到一个横木上他的血量都有可能发生变化，当横木上放着食物的时候，man的血回increase，如果是障碍之类的就损耗血量。

题目分析：在这里我们要处理的问题只有两个：1）如何才能找到包含当前区间的左，右端点的最近 的区间  2）如何跳才能剩下最多血量到达地面。

解决方案：首先按横木高度 进行升序排序，然后从低往高 进行插入，并且 查询包含其左或者右端点的 最近的 下面的区间：查找每块木板左边和右边的木板时只需要在线段树上找左边和右边坐标被谁覆盖就好了；

然后就是选择最优的操作方案：dp方程：dp[left]=max(dp[left],dp[i]+w[left]);  在这里详细的解释一下各个变量的 实际意义：dp[left]是指没有经过第i块横木 跳下来的的方案的血量，dp[i]表示跳到第i个横木所剩下的血，w[left]是指left这个横木上所消耗的血，dp[i]+w[left]是指经过第i个横木然后跳到left上的方案，dp方程就是为了 在这两大类方案中选择最优的！！

代码如下：

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

struct TREE{
	int a,b;
	int color;
}tree[300000];

struct node{
	int x,y,h;
	int left,right,w;
}s[300000];

int dp[100000];

int cmp(struct node a,struct node b){
	return a.h<b.h;
}

int Build(int x,int y,int num){
	tree[num].a=x;	tree[num].b=y;
	tree[num].color=0;
	if(x==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}

int modify(int x,int y,int num,int flag){
	if(x<=tree[num].a&&y>=tree[num].b){
		tree[num].color=flag;
		return 0;
	}
	if(tree[num].color!=-1){
		tree[num+num+1].color=tree[num+num].color=tree[num].color;
		tree[num].color=-1;
	}
	int mid=(tree[num].a+tree[num].b)/2;
	if(x<=mid)
		modify(x,y,num+num,flag);
	if(y>=mid+1)
		modify(x,y,num+num+1,flag);
}

int search(int pos,int num){
	if(tree[num].color!=-1)
		return tree[num].color;
	int mid=(tree[num].a+tree[num].b)/2;
	if(pos<=mid)
		search(pos,num+num);
	else if(pos>=mid+1)
		search(pos,num+num+1);
}

int main(){
	int i,n,maxn;
	Build(1,100000,1);
	while(scanf("%d",&n)!=EOF){
		maxn=0;
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++){
			scanf("%d %d %d %d",&s[i].h,&s[i].x,&s[i].y,&s[i].w);
			if(maxn<s[i].y)
				maxn=s[i].y;
		}
		modify(1,maxn,1,0);
		sort(s+1,s+1+n,cmp);
		for(i=1;i<=n;i++){
			s[i].left=search(s[i].x,1);
			s[i].right=search(s[i].y,1);
			modify(s[i].x,s[i].y,1,i);
		}
		dp[n]=100+s[n].w;
		for(i=n;i>=0;i--){
			if(dp[i]>0){//在这里如果dp[i]小于等于0就是说经过i块横木是不明智的选择，就直接忽略掉了！！
				dp[s[i].left]=max(dp[s[i].left],dp[i]+s[s[i].left].w);
				dp[s[i].right]=max(dp[s[i].right],dp[i]+s[s[i].right].w);
			}
		}
		if(dp[0]>0)
			printf("%d\n",dp[0]);
		else
			printf("-1\n");
	}
	return 0;
}

题目分析：在一个很长的节点序列上（长度最大可以到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;
}