77 lines
1.8 KiB
C++
77 lines
1.8 KiB
C++
#include <cstdio>
|
||
#include <cstring>
|
||
#include <algorithm>
|
||
|
||
using namespace std;
|
||
|
||
//快读
|
||
int read() {
|
||
int x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
|
||
const int N = 50000 + 10;
|
||
|
||
int m = 1, n;
|
||
int d[N << 2];
|
||
|
||
//区间查询
|
||
int query(int l, int r) {
|
||
int ans = 0;
|
||
for (l = l + m - 1, r = r + m + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
|
||
if (~l & 1) ans += d[l ^ 1]; // l是偶数
|
||
if (r & 1) ans += d[r ^ 1]; // r是奇数
|
||
}
|
||
return ans;
|
||
}
|
||
|
||
//单点增加
|
||
void add(int x, int c) {
|
||
d[m + x] += c;
|
||
for (int i = (m + x) >> 1; i; i >>= 1) d[i] = d[i << 1] + d[i << 1 | 1];
|
||
}
|
||
|
||
void build(int n) {
|
||
memset(d, 0, sizeof d);
|
||
for (m = 1; m < n;) m <<= 1; // 强行开够（大于n）方便二进制访问叶节点
|
||
for (int i = 1; i <= n; i++) d[m + i] = read(); //初始值
|
||
for (int i = m; i; i--) d[i] = d[i << 1] + d[i << 1 | 1]; //待所有叶子节点有值后，统一执行一次向上数据统计信息汇总
|
||
}
|
||
|
||
int main() {
|
||
//文件输入输出
|
||
#ifndef ONLINE_JUDGE
|
||
freopen("HDU1166.in", "r", stdin);
|
||
#endif
|
||
int k = read();
|
||
|
||
for (int q = 1; q <= k; q++) {
|
||
n = read();
|
||
//构建zkw线段树
|
||
build(n);
|
||
|
||
printf("Case %d:\n", q);
|
||
|
||
char op[10];
|
||
while (scanf("%s", op)) {
|
||
if (op[0] == 'E') break;
|
||
int l = read(), r = read();
|
||
if (op[0] == 'Q')
|
||
printf("%d\n", query(l, r));
|
||
else if (op[0] == 'A')
|
||
add(l, r);
|
||
else if (op[0] == 'S')
|
||
add(l, -r);
|
||
}
|
||
}
|
||
return 0;
|
||
} |