POJ2155: Matrix

概要

N次正方行列があり,初期状態ではすべての成分が0である.
T個のクエリが来て,内容は

  • (x1,y1),(x2,y2)で定まる矩形領域に反転操作を行う.
  • (x1,y1)の成分を答える

である.

解法

2次元のBITを用意する.これは,(1,1),(x,y)によって定まる矩形領域の値を合計したものを返す.
更新のときは,(x1,y1),(x1,y2+1),(x2+1,y1),(x2+1,y2+1)のそれぞれに1を加える.(中央二つは引き算のため.2を法とする演算であるから,加算と減算は等価である)
こうすると,(1,1),(x,y)の範囲の合計が(x,y)の値になる.

二次元平面上に矩形上に値vを足しこむとき,左下と右上にvをたし,左上と右下に-vを足しておいて最後にまとめて計算するテクニックをBITに応用したもの.

const int MAX_T = 50010;

int X, N, T;
int q[MAX_T];
int X1[MAX_T], Y1[MAX_T], X2[MAX_T], Y2[MAX_T];
int bit[1010][1010];

int get(int x, int y){
    int res = 0;
    int tx = x;
    while(y>0){
        x = tx;
        while(x>0){
            res = (res + bit[y][x]) % 2;
            x -= x & -x;
        }
        y -= y & -y;
    }
    return res;
}
void update(int x, int y, int v){
    int tx = x;
    while(y<=N){
        x = tx;
        while(x<=N){
            bit[y][x] = (bit[y][x] + v) % 2;
            x += x & -x;
        }
        y += y & -y;
    }
}

void solve(){
    memset(bit, 0, sizeof(bit));
    for(int i = 0; i < T; ++i){
        if(q[i] == 'Q'){
            int x = X1[i], y = Y1[i];
            printf("%d\n", get(x, y));
        }
        else{
            update(X1[i], Y1[i], 1);
            update(X1[i], Y2[i]+1, 1);    // v-1=v+1 (mod 2)
            update(X2[i]+1, Y1[i], 1);
            update(X2[i]+1, Y2[i]+1, 1);
        }
    }
}
int main(){
    scanf("%d", &X);
    for(;X>0;--X){
        scanf("%d%d", &N, &T);
        for(int i = 0; i < T; ++i){
            char buf[8];
            scanf("%s%d%d", buf, X1+i, Y1+i);
            q[i] = buf[0];
            if(q[i] == 'C'){
                scanf("%d%d", X2+i, Y2+i);
            }
        }
        solve();
        if(X > 1) printf("\n");
    }
    return 0;
}