题目大意：就是给出两种指令操作，
1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).

题目分析：首先建树，树节点有三个域，分别为左右端点r,l,与代表颜色的color。首先声明，当color等于0的时候表示被多种颜色覆盖了。

更新：首先如果在查找的过程中遇到当前区间的颜色大于0，也就是说这个区间已经被完全染色过，那么就把这个区间的颜色值往下传递，然后把这个区间的颜色值color赋值为0，继续往下查找，也就是常规的三种情况：左子树，右子树，或者左右子树混合的

直到当前区间的跟我的所要更新的区间吻合，停止往下更新！进行染色，也就是把color值附给他，还有一种情况就是：当前区间的color值大于0并且等于我所要染色的颜色值，这样也可以停止往下更新！

计数：在往下计数的时候，如果遇到color值大于0的直接把他在hash[]表里的映射赋值为1，这样防止重复计数！如果color==0；就继续往下计数。又是常规的三种情况！

源程序+部分注释：

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

struct node{
	int a,b,color;
}s[400000];
int h[60];
int Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	s[num].color=1;
	if(x==y)
		return 0;
	else{
		Build(x,(x+y)/2,num+num);
		Build((x+y)/2+1,y,num+num+1);
	}
}

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

int getsum(int x,int y,int num){
	if(s[num].color>0){
		h[s[num].color]=1;
		return 0;
	}
	else{
		if(y<=(s[num].a+s[num].b)/2)
			getsum(x,y,num+num);
		else if(x>(s[num].a+s[num].b)/2)
			getsum(x,y,num+num+1);
		else{
			getsum(x,(s[num].a+s[num].b)/2,num+num);
			getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
		}
	}
}

int main(){
	int l,t,cas,i,j,sum;
	int x,y,color;
	char c;
	scanf("%d %d %d",&l,&t,&cas);
		memset(h,0,sizeof(h));
		Build(1,l,1);
		for(j=1;j<=cas;j++){
			sum=0;
			cin>>c;
			if('P'==c){
				scanf("%d %d",&x,&y);
				getsum(x,y,1);
				for(i=1;i<=t;i++)
					cout<<h[i];
				cout<<endl;
				for(i=1;i<=t;i++)
					sum+=h[i];
				printf("%d\n",sum);
				memset(h,0,sizeof(h));
			}
			else if('C'==c){
				scanf("%d %d %d",&x,&y,&color);
				modify(x,y,1,color);
			}
		}
	return 0;
}

题目大意：给你一个连续的自然数序列，
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)

中逆序数最大的是多少。

其实用树状数组求这个是非常方便速度的，但是为了锻炼线段树  我还是用线段树写了。

程序+部分注释：

#include<iostream>
#include<stdio.h>
using namespace std;
int ans=0;
struct node{
	int a,b;
	int v;
}s[20000];

int t[5002];

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

int modify(int num,int ide ){
	if(s[num].a==s[num].b){
		s[num].v=1;
		return 0;
	}
	else{
		if(ide<=(s[num].a+s[num].b)/2)
			modify(num+num,ide);
		else if(ide>(s[num].a+s[num].b)/2)
			modify(num+num+1,ide);
		s[num].v=s[num+num].v+s[num+num+1].v;
	}
}

int getsum(int x,int y,int num){
	if(x==s[num].a&&y==s[num].b){
		ans+=s[num].v;
		return 0;
	}
	else{
		if(y<=(s[num].a+s[num].b)/2)
			getsum(x,y,num+num);
		else if(x>(s[num].a+s[num].b)/2)
			getsum(x,y,num+num+1);
		else{
			getsum(x,(s[num].a+s[num].b)/2,num+num);
			getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
		}
	}
}

int main(){
	int n,i,min;
	while(scanf("%d",&n)!=EOF){
		ans=0;
		for(i=1;i<=n;i++)
			scanf("%d",&t[i]);
		Build(1,n,1);
		for(i=n;i>=1;i--){
			getsum(1,t[i]+1,1);
			modify(1,t[i]+1);
                        求出总和
		}
		min=ans;
		for(i=1;i<=n-1;i++){
			ans=ans-t[i]+n-t[i]-1;
                        //因为数组是连续的自然数，从0到n所以
                       //t[i]移动到最后面去，就减少了t[i]个逆                    
                         //序对，同时也与以前是后面的而且比他大的数构成了
                           //N-（t[i]+1）组逆序对
			if(ans<min)
				min=ans;
		}
		printf("%d\n",min);
	}
	return 0;
}

题目大意：给一组棍子染色，不同的颜色有不同的值，执行一系列的区间染色后，问这组棍子的总值是多少。

题目分析：建树：节点的域有左右节点和颜色，a,b,v；v=0时表示这个区间由多种颜色覆盖。

更新的时候，如果更新区间比当前区间小，并且当前区间的颜色大于0，说明已经被完全染色，就把该区间颜色传递到左右子树上，该区间染色为0，然后根据更新区间的大小，在左右子树上去搜索。

求和的时候遇到区间的v>0的时候说明完全被染色过了，就把区间的长度乘以颜色的值加到总和里面去，然后结束这个方向的递归查询，

源程序+部分注释：

#include<stdio.h>
#include<iostream>
using namespace std;
struct node{
	int a,b,v;
}s[400000];

int t[150000],ans;

void Build(int x,int y,int num){
	s[num].a=x;	
	s[num].b=y;
	s[num].v=1;
	if(x==y)
		return ;	
	else{
		Build(x,(x+y)/2,num+num);
		Build((x+y)/2+1,y,num+num+1);
	}
}

void modify(int x,int y,int num,int value){
	if(x==s[num].a&&s[num].b==y){
		s[num].v=value;
		return ;
	}
	if(s[num].v==value)
		return ;
	if(s[num].v>0){
		s[2*num].v=s[2*num+1].v=s[num].v;
		s[num].v=0;
              //值往下传递。0代表混合染色
	}
	if(y<=(s[num].a+s[num].b)/2){
		modify(x,y,num+num,value);
	}
	else if(x>(s[num].a+s[num].b)/2)
		modify(x,y,num+num+1,value);
	else{	int mid=(s[num].a+s[num].b)/2;
		modify(x,mid,num+num,value);
		modify(mid+1,y,num+num+1,value);
	}
		
}

int getsum(int x,int y,int num){
	if(s[num].v>0){
		ans+=(s[num].b-s[num].a+1)*s[num].v;
		return 0;
	}
	else{
		if(y<=(s[num].a+s[num].b)/2)
			getsum(x,y,num+num);
		else if(x>(s[num].a+s[num].b)/2)
			getsum(x,y,num+num+1);
		else{
			getsum(x,(s[num].a+s[num].b)/2,num+num);
			getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
		}
	}

}

int main(){
	int cas,n,k,i,v;
	int x,y,count;
	cin>>cas;
	k=1;
	while(cas--){
		ans=0;
		cin>>n;
		for(i=1;i<=n;i++){
			t[i]=1;
		}
		Build(1,n,1);
		scanf("%d",&count);
		for(i=1;i<=count;i++){
			scanf("%d %d %d",&x,&y,&v);
			modify(x,y,1,v);
		}
		getsum(1,n,1);
		printf("Case %d: The total value of the hook is %d.\n",k++,ans);
	}
	return 0;
}

题目分析：学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

有一次参加农大月赛，因为对线段树的求区间最值的更新还是不熟练，所以出错了！缅怀！

#include<stdio.h>
int Max(int a,int b)
{
    return a>b?a:b;
}
struct node{
	int max,a,b;
}s[800000];

int t[200010];

void Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	if(x==y){
		s[num].max=t[x];
		return ;
	}
	else{
		Build(x,(x+y)/2,num+num);
		Build(((x+y)/2)+1,y,num+num+1);
		s[num].max=Max(s[num+num].max,s[num+num+1].max);
	}
}
int Query_max(int x,int y,int idx)
{
    if(x<=s[idx].a && s[idx].b<=y)
    {
        return s[idx].max;
    }
    if(y<=s[idx*2].b) return Query_max(x,y,idx*2);
    else if(x>=s[idx*2+1].a) return Query_max(x,y,idx*2+1);
    else return Max(Query_max(x,s[idx*2].b,idx*2),Query_max(s[idx*2+1].a,y,idx*2+1));
}
int modify(int x,int y,int num){
	if(s[num].a==x&&s[num].b==x){
		s[num].max=y;	
		return 0;
	}
	else{
		if(x<=s[num+num].b)
			modify(x,y,num+num);
		else 
			modify(x,y,num+num+1);
		s[num].max=Max(s[num+num].max,s[num+num+1].max);
	}
}

int main(){
	int n,cas,i,x,y;
	char c;
	while(scanf("%d %d",&n,&cas)!=EOF){
		for(i=1;i<=n;i++)
			scanf("%d",&t[i]);
		Build(1,n,1);
		while(cas--){
			getchar();
			scanf("%c %d %d",&c,&x,&y);
			if(c=='Q'){
				printf("%d\n",Query_max(x,y,1));		
			}
			else {
				modify(x,y,1);
			}
		}
		
	}
	return 0;
}

题目大意：(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
                (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
                (3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
                (4)End 表示结束，这条命令在每组数据最后出现;

题目分析：目的是纪念我线段树的开端，也是为了今后的回顾。其实就是基本操作，更新跟建树。

源程序+部分注释：

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

struct node{
	int sum,a,b;
}s[140000];

int t[52005],ans;

void Build(int x,int y,int num){
	s[num].a=x;  s[num].b=y;
	if(x==y)
		s[num].sum=t[x];
	else{
		Build(x,(x+y)/2,num+num);
		Build(((x+y)/2)+1,y,num+num+1);
		s[num].sum=s[num+num].sum+s[num+num+1].sum;
	}
}

void Query(int x,int y,int num){
	if(x<=s[num].a&&y>=s[num].b)
		ans+=s[num].sum;
	else{
		if(x>(s[num].a+s[num].b)/2)
			Query(x,y,num+num+1);
		else if(y<=(s[num].a+s[num].b)/2)
			Query(x,y,num+num);
		else{
			Query(x,y,num+num);
			Query(x,y,num+num+1);
		}
	}
}

void Add(int x,int y,int num){
	s[num].sum+=y;
	if(s[num].a==x&&s[num].b==x)
		return ;
	else{
		if(x<=(s[num].a+s[num].b)/2)
			Add(x,y,num+num);
		else
			Add(x,y,num+num+1);
	}
}

int Sub(int x,int y,int num){
	s[num].sum-=y;
	if(s[num].a==x&&s[num].b==x)
		return 0;
	else{
		if(x<=(s[num].a+s[num].b)/2)
			Sub(x,y,num+num);
		else
			Sub(x,y,num+num+1);
	}
}

int main(){
	int cas,n,i,k,x,y;
	char c[20];
	scanf("%d",&cas);
	k=1;
	while(cas--){
		scanf("%d",&n);
		for(i=1;i<=n;i++){
			scanf("%d",&t[i]);
		}
		Build(1,n,1);
		cout<<"Case "<<k<<":"<<endl;
		k++;
		while(1){
			scanf("%s",c);
			if(c[0]=='E')
				break;
			scanf("%d %d",&x,&y);
			if(c[0]=='Q'){
				ans=0;
				Query(x,y,1);
				cout<<ans<<endl;			
			}
			else if(c[0]=='A'){
				Add(x,y,1);
			}
			else{
				if(c[0]=='S')
					Sub(x,y,1);
			}
		}
	}
	return 0;
}

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define max 100000
#define lowbit(x) (x&(-x))
using namespace std;
const int N=100001;
int c[100005],a[100005];

int getsum(int x){
	int sum=0;
	while(x){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

int modify(int x,int num){
	while(x<=N){
		c[x]+=num;
		x+=lowbit(x);
	}
	return 0;
}

int main(){
	int n,i,left,right,md;
	int sign,m,t,num1;
	while(scanf("%d",&n)!=EOF){
		memset(c,0,sizeof(c));
		memset(a,0,sizeof(a));
		while(n--){
			scanf("%d",&sign);
			if(sign==0){
				scanf("%d",&t);
				a[t]++;
				modify(t,1);
			}
			else if(sign==1){
				scanf("%d",&t);
				if(!a[t])
					cout<<"No Elment!"<<endl;
				else{
					a[t]--;
					modify(t,-1);
				}
			}
			else if(sign==2){
				scanf("%d %d",&m,&t);
				num1=getsum(m)+t;
				if(num1>getsum(max)){
					cout<<"Not Find!"<<endl;
				        continue;				
				}
				left=m+1;
				right=max;
				while(right-left>1){
					md=getsum((right+left)/2);
					if(md>num1){
						right=(right+left)/2;
					}
					else if(md<num1){
						left=(right+left)/2;
					}
					else {
						if(a[(right+left)/2]){
							cout<<(right+left)/2<<endl;
							break;
						}
						else
							right=(right+left)/2;
					}
				}
				if(right-left<=1){
					if(getsum(left)>=num1)
						cout<<left<<endl;
					else
						cout<<right<<endl;
				}
			}
			
		}
	}
	return 0;
}

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

解题分析：这里跟求面积所要求的基本操作是一致的。对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;
}

题目大意：给出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;
}