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

Posted by xiaodao
Category: POJ