2015-06-08
问题简述：
原题的题意相当于有一些连续摆放的箱子，里面装着球，球的数量可以加减，现要查询几个连续的箱子里球的总数，其中存在放球和拿球的操作。
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
解题思路：
查询区间和的问题，可以使用线段树。
最初的输入相当于构建线段树的过程；每一次的加减相当于对线段树进行更新；最后使用线段树的查询区间和算法直接得出答案。
源代码：
/*
OJ: HDOJ
ID: forever
TASK: 1166.敌兵布阵
LANG: C++
NOTE: 线段树
*/
#include <cstdio> const int MAX=;
int a[MAX];
char str[]; void build(int l,int r,int flag) {
if(l==r) {
scanf("%d",&a[flag]);
return;
}
int m=(l+r)/;
build(l,m,flag*);
build(m+,r,flag*+);
a[flag]=a[flag*]+a[flag*+];
} void update(int x,int y,int l,int r,int flag) {
if(l==r) {
a[flag]+=y;
return;
}
int m=(l+r)/;
if(x<=m)
update(x,y,l,m,flag*);
else
update(x,y,m+,r,flag*+);
a[flag]=a[flag*]+a[flag*+];
} int query(int x,int y,int l,int r,int flag) {
if(x<=l&&r<=y)
return a[flag];
int m=(l+r)/;
int ans=;
if(x<=m)
ans+=query(x,y,l,m,flag*);
if(y>m)
ans+=query(x,y,m+,r,flag*+);
return ans;
} int main()
{
int t,n,x,y,k=;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
build(,n,);
printf("Case %d:\n",k++);
while(scanf("%s",str)&&str[]!='E') {
scanf("%d %d",&x,&y);
if(str[]=='Q')
printf("%d\n",query(x,y,,n,));
else if(str[]=='A')
update(x,y,,n,);
else if(str[]=='S')
update(x,-y,,n,);
}
}
return ;
}