|
|
題目鏈接： http://acm.hdu.edu.cn/showproblem.php?pid=1166
  /**//*
 題意：
給定N(N <= 50000)個數(shù), 表示敵人有N個工兵營地，接下來有N個正整數(shù), 第
i個正整數(shù)ai代表第i個工兵營地里開始時有ai個人（1<=ai<=50）。
接下來每行有一條命令，命令有4種形式：
(1)Add i j ,i和j為正整數(shù), 表示第i個營地增加j個人（j不超過30）
(2)Sub i j ,i和j為正整數(shù), 表示第i個營地減少j個人（j不超過30）;
(3)Query i j ,i和j為正整數(shù), i<=j，表示詢問第i到第j個營地的總人數(shù);
(4)End 表示結束，這條命令在每組數(shù)據(jù)最后出現(xiàn)
解法：
樹狀數(shù)組 或者 線段樹
思路：
典型的樹狀數(shù)組模板題，Add和Sub是同一個操作，Sub就是Add一個負的值，只
是Sub之前先要判斷這個點有沒有這么多，詢問就是利用樹狀數(shù)組的成段求和。
 */
#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);
}
}
}
}
|