POJ - 2155 (Matrix)

题意：给定一个n*n的0-1矩阵s，初始全部为0，有 q 次操作，涉及两种：

①C x1 y1 x2 y2 :将这个矩形区域内的数0变成1，1变成0；

②Q x y :查询 s[x][y]；

 

分析：蛮明显的二维差分，因为查询和更新交替进行，所以选择用树状数组维护( 查询和更新都是O(logn) )；

 

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 1E3+10;

int s[N][N],n,q;
int lowbit(int x){return x&(-x);}

void add(int x,int y,int op){
	for(int i=x;i<=n;i+=lowbit(i)){
		for(int j=y;j<=n;j+=lowbit(j)){
			s[i][j]+=op;
		}
    } 
}
int query(int x,int y){
	int ans=0;
    for(int i=x;i>0;i-=lowbit(i)){
    	for(int j=y;j>0;j-=lowbit(j)){
    		ans+=s[i][j];
		}
	} 
	return ans;
}


int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		memset(s,0,sizeof(s));
		char c[3];int x1,y1,x2,y2;
		while(q--){
			scanf("%s",c);
			if(c[0]=='C'){
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				add(x1,y1,1);
			    add(x1,y2+1,-1);
			    add(x2+1,y1,-1);
			    add(x2+1,y2+1,1);
			}
			else{
				scanf("%d%d",&x1,&y1);
				if(query(x1,y1)%2) puts("1");
				else puts("0");
			}
		}
		puts("");
	}
}