POJ 2528（Mayor's posters）经典线段树问题

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