POJ 2777（Count Color） 经典染色问题

题目大意：就是给出两种指令操作，
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;
}