Maximum Winter-Contest 2011 F: Many time Segment Sum

keyword

BIT　C++

問題概要

3次元のBIT。

解法

やるだけ。蟻本に載ってるし。

const int MAX = 55;

int64 BIT[MAX][MAX][MAX];

int64 sum1(int x, int64 _XS[MAX]){
    if(!x) return 0;
    int64 _R=0;
    for(;x;x-=x&-x)_R+=_XS[x];
    return _R;
}
int64 sum1(int x1, int x2, int64 _XS[MAX]){
    return sum1(x2,_XS)-sum1(x1-1,_XS);
}
void add1(int x, int a, int64 _XS[MAX]){
    for(;x<=MAX;x+=x&-x)_XS[x]+=a;
}

int64 sum2(int y, int x1, int x2, int64 _XS[MAX][MAX]){
    if(!y) return 0;
    int64 _R=0;
    for(;y;y-=y&-y)_R+=sum1(x1,x2,_XS[y]);
    return _R;
}
int64 sum2(int y1, int y2, int x1, int x2, int64 _XS[MAX][MAX]){
    return sum2(y2,x1,x2,_XS)-sum2(y1-1,x1,x2,_XS);
}
void add2(int y, int x, int a, int64 _XS[MAX][MAX]){
    for(;y<=MAX;y+=y&-y)
        add1(x,a,_XS[y]);
}

int64 sum3(int z, int y1, int y2, int x1, int x2){
    if(!z) return 0;
    int64 _R=0;
    for(;z;z-=z&-z)_R+=sum2(y1,y2,x1,x2,BIT[z]);
    return _R;
}

int64 sum3(int z1, int z2, int y1, int y2, int x1, int x2){
    return sum3(z2,y1,y2,x1,x2)-sum3(z1-1,y1,y2,x1,x2);
}
void add3(int z, int y, int x, int a){
    for(;z<=MAX;z+=z&-z)
        add2(y,x,a,BIT[z]);
}

void proc(){
    int Q;
    scanf("%d ",&Q);
    for(int i=0; i<Q; i++){
        char op;
        scanf("%c",&op);
        if(op == '+' || op == '-'){
            int x, y, z, a;
            scanf("%d%d%d%d ",&x,&y,&z,&a);
            if(op=='-') a = -a;
            add3(z,y,x,a);
        }
        else{
            int x1,x2,y1,y2,z1,z2;
            scanf("%d%d%d%d%d%d ",&x1,&y1,&z1,&x2,&y2,&z2);
            printf("%lld\n",sum3(z1,z2,y1,y2,x1,x2));
        }
    }
}

int main(){
    int x,y,z,op;
    while(scanf("%d%d%d ",&x,&y,&z)!=EOF){
        if(!x && !y && !z) break;
        for(int i=0; i<MAX; i++)for(int j=0; j<MAX; j++)for(int k=0; k<MAX; k++)
            BIT[i][j][k] = 0;
        for(int i=1; i<=z; i++){
            for(int j=1; j<=y; j++){
                for(int k=1; k<=x; k++){
                    int a;
                    scanf("%d ",&a);
                    add3(i,j,k,a);
                }
            }
        }
        proc();
    }
    return 0;
}