hdu1166 敵兵布陣

傳送門

思路

裸題

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 50010;

ll tr[N];
ll ans[N];
int n;

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

void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}

ll sum(int x){
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

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