传送门：https://vjudge.net/problem/POJ-2155
题意：给你一个n*n的01矩阵，初始时为0，然后每次有两种操作，第一种是一个子矩阵的翻转，另一种是询问某点的值。
这题是从白书上来的，增加了我对二维数组的理解。
我们先想一下一维的情况，要实现一个区间增加某一个值，只需要用差分数组，每次实现操作只需要a[l]+1,以及a[r+1]-1，便可。
但是二维用差分数组就有点难受了。但是起码思想是有的，就是一个区域加某值，可以修改它的端点。
那我这里二维的，a[x][y]里面的值表示以（x，y）为左上角，（n,n)为右下角的矩阵翻转的次数，所以根据容斥原理可以解决第一个操作
（这一篇博文解释的很好了：https://blog.csdn.net/acm_fish/article/details/69842523）
然后询问(x,y)的值，其实也就是问(x,y)的翻转次数，根据上面a[x][y]的含义可以知道，求以(x,y),(0,0)的矩阵的值的和便可。
这里用二维树状数组，其实也就是多了一个for而已
1 // Cease to struggle and you cease to live 2 #include <iostream> 3 #include <cmath> 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <vector> 9 #include <set> 10 #include <map> 11 #include <stack> 12 using namespace std; 13 typedef long long ll; 14 const int N=1000+8; 15 int n; 16 int tr[N][N]; 17 char s[3]; 18 void add(int x,int y){ 19 for(int tx=x;tx<=n;tx+=tx&-tx){ 20 for(int ty=y;ty<=n;ty+=ty&-ty){ 21 ++tr[tx][ty]; 22 } 23 } 24 } 25 int sum(int x,int y){ 26 int res=0; 27 for(int tx=x;tx;tx-=tx&-tx){ 28 for(int ty=y;ty;ty-=ty&-ty){ 29 res+=tr[tx][ty]; 30 } 31 } 32 return res; 33 } 34 int main() { 35 int T;scanf("%d",&T); 36 for(int t=1;t<=T;++t){ 37 memset(tr,0,sizeof(tr)); 38 scanf("%d",&n); 39 int qn;scanf("%d",&qn); 40 for(int i=1;i<=qn;++i){ 41 scanf("%s",s); 42 int x1,x2,y1,y2; 43 scanf("%d%d",&x1,&y1); 44 if(s[0]==‘C‘){ 45 scanf("%d%d",&x2,&y2); 46 add(x1,y1);add(x2+1,y2+1);add(x1,y2+1);add(x2+1,y1); 47 } 48 else{ 49 printf("%d\n",sum(x1,y1)%2); 50 } 51 } 52 cout<<endl; 53 } 54 return 0; 55 }
原文：https://www.cnblogs.com/xiaobuxie/p/10887384.html
