|
|
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1166
  /**//*
 题意：
给定N(N <= 50000)个数, 表示敌人有N个工兵营地，接下来有N个正整数, 第
i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(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 表示结束，这条命令在每组数据最后出现
解法：
树状数组 或者 线段树
思路：
典型的树状数组模板题，Add和Sub是同一个操作，Sub就是Add一个负的值，只
是Sub之前先要判断这个点有没有这么多，询问就是利用树状数组的成段求和。
 */
#include <iostream>
using namespace std;
#define maxn 1000010
int c[maxn], n;
int a[maxn];
char ch[100];
int lowbit(int x)  {
return x & (-x);
}
void Add(int x, int add) {
  while(x <= n) {
c[x] += add;
x += lowbit(x);
 }
}
int sum(int x) {
int s = 0;
while(x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}
int main() {
int t, as, bs, i, q = 1;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
memset(c, 0, sizeof(c));
for(i = 1; i <= n ;i++) {
scanf("%d", &a[i]);
Add(i, a[i]);
}
printf("Case %d:\n", q++);
while(scanf("%s" , ch) != EOF) {
if(!strcmp(ch, "End"))
break;
else if(!strcmp(ch, "Query")) {
scanf("%d%d", &as, &bs);
printf("%d\n", sum(bs) - sum(as - 1));
}else if(!strcmp(ch, "Add")) {
scanf("%d%d", &as, &bs);
Add(as, bs);
} else if(!strcmp(ch, "Sub")) {
scanf("%d%d", &as, &bs);
Add(as, -bs);
}
}
}
}
|