HDU 1698（Just a Hook）

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

题目分析：建树：节点的域有左右节点和颜色，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;
}