Brief description:

… 給定一個 0/1 矩陣，初始全是 0，動態維護以下操作。

• C x1 y1 x2 y2: 將一個子矩陣取反。
• Q x y: 詢問單個位置的狀態。

Analysis:

… 略（二維樹狀數組。。。

const int N = 1001;
bool C[N][N];
int n, m;

void Modify(int x, int y){
	while (x > 0){
		for (int t = y; t > 0; t -= low_bit(t))
			C[x][t] ^= 1;
		x -= low_bit(x);
	}
}

bool Query(int x, int y){
	bool res = false; while (x <= n){
		for (int t = y; t <= n; t += low_bit(t))
			res ^= C[x][t];
		x += low_bit(x);
	}
	return res;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

	Rush{
		int x1, y1, x2, y2; char cmd;

		RST(C); RD(n); DO_C(RD()){
			RC(cmd); if (cmd =='C'){
				RD(x1, y1, x2, y2);
				Modify(x2, y2), Modify(x2, y1-1), Modify(x1-1, y2), Modify(x1-1, y1-1);
			}
			else {
				RD(x1, y1);
				OT(Query(x1, y1));
			}
		}

		puts("");
	}
}

External link:

http://poj.org/problem?id=2155