HDU 1166(敌兵布阵)

spoiler posted @ 2011年4月11日 22:49 in ACM经典题目之线段树 , 1584 阅读

题目大意:(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;
}

 


登录 *


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