HDU 1166 敌兵布阵

HDU_1116

    用线段树支持单点修改和区间求和即可。

#include<stdio.h>
#include<string.h>
#define MAXD 50010
int N, M, tree[4 * MAXD];
char b[20];
void solve()
{
int i, j, k, res, s, t;
    scanf("%d", &N);
for(M = 1; M < N + 1; M <<= 1);
    memset(tree, 0, sizeof(tree));
for(i = 1, j = M + 1; i <= N; i ++, j ++)
        scanf("%d", &tree[j]);
for(i = M - 1; i; i --)
        tree[i] = tree[2 * i] + tree[2 * i + 1];
for(;;)
    {
        scanf("%s", b);
if(b[0] == 'E')
break;
if(b[0] == 'A')
        {
            scanf("%d%d", &i, &k);
            i += M;
for(; i ^ 1; i >>= 1)
                tree[i] += k;
        }
else if(b[0] == 'S')
        {
            scanf("%d%d", &i, &k);
            i += M;
for(; i ^ 1; i >>= 1)
                tree[i] -= k;
        }
else
        {
            scanf("%d%d", &s, &t);
            s = s + M - 1, t = t + M + 1;
            res = 0;
for(; s ^ t ^ 1; s >>= 1, t >>= 1)
            {
if(~s & 1)
                    res += tree[s ^ 1];
if(t & 1)
                    res += tree[t ^ 1];
            }
            printf("%d\n", res);
        }
    }
}
int main()
{
int t, tt;
    scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
    {
        printf("Case %d:\n", tt + 1);
        solve();
    }
return 0;
}