HDU 1698(Just a Hook)

spoiler posted @ 2011年4月11日 23:06 in ACM经典题目之线段树 , 1452 阅读

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

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

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter