hdu 1166単点修正区間クエリー
1798 ワード
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 50005;
int sum[maxn<<2];
void push_up(int root)
{
sum[root] = sum[root << 1] + sum[((root << 1) | 1)];
}
void build(int L, int R, int root)
{
if (L == R) {
scanf("%d", &sum[root]);
return;
}
int mid = (L + R) >> 1;
build(L, mid, root << 1);
build(mid + 1, R, ((root << 1) | 1));
push_up(root);
}
void push_down(int a, int value, int L, int R, int root)
{
if (L == R) {
sum[root] += value;
return;
}
int mid = (L + R) >> 1;
if (a <= mid)push_down(a, value, L, mid, root << 1);
else push_down(a, value, mid + 1, R, ((root << 1) | 1));
push_up(root);
}
int query(int l, int r, int L, int R, int root)
{
if (l <= L&&r >= R)return sum[root];
int mid = (L + R) >> 1;
if (r <= mid)return query(l, r, L, mid, root << 1);
else if (l > mid)return query(l, r, mid + 1, R, ((root << 1) | 1));
else return query(l, mid, L, mid, root << 1) + query(mid + 1, r, mid + 1, R, ((root << 1) | 1));
}
int main()
{
int T,n;
scanf("%d", &T);
for (int i = 1; i <= T; i++) {
scanf("%d", &n);
build(1, n, 1);
printf("Case %d:
", i);
char ch[20];
while (scanf("%s",ch))
{
if (ch[0] == 'E')break;
int a, b;
cin >> a >> b;
if (ch[0] == 'A')push_down(a, b, 1, n, 1);
else if (ch[0] == 'S')push_down(a, -b, 1, n, 1);
else if (ch[0] == 'Q')
printf("%d
", query(a, b, 1, n, 1));
}
}
return 0;
}