【HDU1166】敌兵布阵(线段树)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 09 月 17 日

C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.

题意:罗嗦了很多,意思就是说 更新点问线。
题解:可用树状数组,线段树。因为复出练习需要,打打线段树,所以代码有点多,有需求的请耐心看。如果对线段树不太了解请google,另外可以参考另外一篇博文,里边代码有关于线段树的建树、查询、更新的详细注释。

#include<stdio.h>
#include <string.h>
#define MAXLEN 50005
#define LL(X) (X)<<1
#define RR(X) ((X)<<1)+1

struct Node{
	int l,r;
	int num;
}nodes[4*MAXLEN];
int soldiers[MAXLEN];
int buildTree(int l,int r,int n){
	nodes[n].l=l;
	nodes[n].r=r;
	nodes[n].num=0;
	if(l==r){
		return nodes[n].num = soldiers[l];
	}
	int mid=(l+r)>>1;
	return nodes[n].num =buildTree(l,mid,LL(n))+buildTree(mid+1,r,RR(n));
}

int updata(int l,int r,int n,int num){
	if(nodes[n].l==l && nodes[n].r==r){
		return nodes[n].num +=num;
	}
	if(l>=nodes[RR(n)].l)
		return nodes[n].num =updata(l,r,RR(n),num)+nodes[LL(n)].num;
	else if(r<=nodes[LL(n)].r)
		return nodes[n].num =updata(l,r,LL(n),num)+nodes[RR(n)].num;
	else {
		return nodes[n].num =updata(l,nodes[LL(n)].r,LL(n),num)+updata(nodes[RR(n)].l,r,RR(n),num);
	}
}
int query(int l,int r,int n){
	if(nodes[n].l==l && nodes[n].r==r){
		return nodes[n].num;
	}
	if(l>=nodes[RR(n)].l)
		return query(l,r,RR(n));
	else if(r<=nodes[LL(n)].r)
		return query(l,r,LL(n));
	else {
		return query(l,nodes[LL(n)].r,LL(n))+query(nodes[RR(n)].l,r,RR(n));
	}
}

int main(){
	//freopen("1.txt","r",stdin);
	int n,loop,m,l,r;
	char cmd[8];
	scanf("%d",&n);
	loop=n;
	while(n--){
		printf("Case %d:\n",loop-n);
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
			scanf("%d",&soldiers[i]);
		buildTree(1,m,1);
		while(1){
			scanf("%s",cmd);
			if(strcmp(cmd,"End")==0)
				break;
			scanf("%d%d",&l,&r);
			if(strcmp(cmd,"Query")==0)
				printf("%d\n",query(l,r,1));
			else if(strcmp(cmd,"Add")==0)
				updata(l,l,1,r);
			else if(strcmp(cmd,"Sub")==0)
				updata(l,l,1,-r);
		}
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日