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