題意：第一行一個整數T，表示有T組數據。每組數據第一行一個正整數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 表示結束，這條命令在每組數據最後出現; 每組數據最多有40000條命令 ——>>直接BIT，就像模版題。 [cpp] #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 50000 + 10; int a[maxn], lowerbit[maxn], C[maxn], N; int sum(int x) //BIT前x項和 { int ret = 0; while(x > 0) { ret += C[x]; x -= lowerbit[x]; } return ret; } void add(int x, int d) //BIT修改——加 { while(x <= N) { C[x] += d; x += lowerbit[x]; } } void sub(int x, int d) //BIT修改——減 { while(x <= N) { C[x] -= d; x += lowerbit[x]; } } int main() { int T, cnt = 1, i, j; for(i = 0; i < maxn; i++) lowerbit[i] = i&(-i); scanf("%d", &T); while(T--) { memset(C, 0, sizeof(C)); scanf("\n%d\n", &N); for(i = 1; i <= N; i++) { scanf("%d", &a[i]); add(i, a[i]); } char s[7]; printf("Case %d:\n", cnt++); while(~scanf("%s", s)) { if(strcmp(s, "End") == 0) break; scanf("%d%d", &i, &j); if(strcmp(s, "Query") == 0) printf("%d\n", sum(j) - sum(i-1)); else if(strcmp(s, "Add") == 0) add(i, j); else sub(i, j); } } return 0; }
