题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166
思路分析:该问题为动态连续和查询问题,使用数组数组可以解决;也可使用线段树解决该问题;
代码如下:
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; const int MAX_N = + ;
int c[MAX_N]; inline int Lowbit(int x) { return x & -x; }
inline int Sum(int x)
{
int ret = ;
while (x) {
ret += c[x];
x -= Lowbit(x);
}
return ret;
} inline void Add(int x, int d, int n)
{
while (x <= n) {
c[x] += d;
x += Lowbit(x);
}
} int main()
{
int a = , b = , ans = , temp = ;
int test_case = , case_id = , n = ;
char command[]; scanf("%d", &test_case);
while (test_case--) {
scanf("%d", &n);
memset(c, , sizeof(c));
for (int i = ; i <= n; ++ i) {
scanf("%d", &temp);
Add(i, temp, n);
}
printf("Case %d:\n", ++case_id);
while(scanf("%s", command) != EOF && command[] != 'E') {
scanf("%d %d", &a, &b);
if (command[] == 'Q') {
ans = Sum(b) - Sum(a - );
printf("%d\n", ans);
} else if (command[] == 'A') {
Add(a, b, n);
} else {
Add(a, -b, n);
}
}
}
return ;
}