概要
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; }