【题解】HDOJ P1166【敌兵布阵】

背景

从某大神的分卷开始做的第一题,一开始就套了线段树,发现写挂了(提交无限RE),后面又换zkw线段树,还是挂了,后来又重写了一次,仍然挂了,这回连样例都过不了了,(捂脸,菜不成声)。
于是就心态爆炸准备分块,不过转念一想,都不用线段树了,用什么分块,直接上树状数组,好写又能AC。

分析

水体一道,属于看了就会写的那种

代码

#include<cstdio>
#include<cstring>

const int MAXN = 5e4 + 6;
int A[MAXN],C[MAXN],n;

inline int lowbit(int x){return x & -x;}

inline int sum(int x){int ans = 0;for(;x;x -= lowbit(x)) ans += C[x];return ans;}
void add(int x,int y){for(;x <= n;x += lowbit(x)) C[x] += y;}
inline void init(){memset(C,0,sizeof(C));for(int i = 1;i <= n;i++) add(i,A[i]);}

int main(){
    int T,l,r;scanf("%d",&T);
    for(int GG = 1;GG <= T;GG++){
        printf("Case %d:\n",GG);scanf("%d",&n);
        for(int i = 1;i <= n;i++) scanf("%d",&A[i]);
        init();char op[10];
        while(scanf("%s",op) && op[0] != 'E'){
            scanf("%d %d",&l,&r);
            if(op[0] == 'Q') printf("%d\n",sum(r) - sum(l - 1));
            else if(op[0] == 'A') add(l,r);
            else add(l,-r);
        }
    }
    return 0;
}