首页 > 代码库 > hdu 1166

hdu 1166

  只是纪念1A

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define maxx 50050
int bit[maxx],a[maxx];
int n;
int aa,bb;
char s[10];

int sum(int i){
    int s=0;
    while (i>0){
        s+=bit[i];
        i-=i&-i;
    }
    return s;
}

int add(int i,int x){
while(i<=n){
    bit[i]+=x;
    i+=i&-i;
}
}

int main(){
    int T;
    while(scanf("%d",&T)==1){
        int cases=1;
        while (T--){
            scanf("%d",&n);
            memset(bit,0,sizeof(bit));
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
                add(i,a[i]);
            }
            printf("Case %d:\n",cases++);
            while(1){
               scanf("%s",s);
               if(s[0]=='Q'){
                scanf("%d%d",&aa,&bb);
                printf("%d\n",sum(bb)-sum(aa)+a[aa]);
               }
               else if(s[0]=='A'){
                scanf("%d%d",&aa,&bb);
                add(aa,bb);
                a[aa]+=bb;
               }
               else if(s[0]=='S'){
                scanf("%d%d",&aa,&bb);
                add(aa,-bb);
                a[aa]-=bb;
               }
               else if(s[0]=='E'){
                break;
               }
            }
        }
    }
}


hdu 1166