原题链接：https://vjudge.net/problem/POJ-2155
题目大意
给定 n* n 矩阵A，其元素为0或1. A [i][j] 表示第i行和第j列中的数字。最初全为0.
我们有两个操作:
-
C x1 y1 x2 y2（1 <= x1 <= x2 <= n，1 <= y1 <= y2 <= n）将左上角为(x1,y1)，右下角为(x2,y2)的矩阵翻转（0变成1，1变成0）。
-
Q x y（1 <= x，y <= n）查询A [x][y]，输出答案。
解析：
思路很简单，只要统计出每个点取反过多少次，当前取反奇数次就变成(1)，偶数次就变成(0)。
可以考虑用二维树状数组维护一个二维差分序列的二维前缀和，将区间修改+单点查询转化为单点查询+单点修改，复杂度降至(O(logn))级别。
初始化差分序列所有值为(0)，对于以(x,y)为左上角顶点，(x',y')为右下角顶点的子矩阵，它应该这样差分：(d(x,y)+1,d(x,y'+1)-1,d(x'+1,y)-1,d(x'+1,y'+1)+1)
举个栗子：
考虑一个二维差分序列：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
我们在某个区间加上(k)：
0 0 0 0 0
0 +x 0 -x 0
0 0 0 0 0
0 -x 0 +x 0
0 0 0 0 0
于是它的二维前缀和就变成了：
0 0 0 0 0
0 x x x 0
0 x x x 0
0 x x x 0
0 0 0 0 0
具体原理的话，可以参考一维差分，或许你可以把它看作二维前缀和的逆运算。
这样就可以方便的维护每一个子矩阵的每一个位置取反的次数。
参考代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define N 1010
using namespace std;
int c[N][N],n;
inline int read()
{
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline void add(int x,int y,int val)
{
for(;x<=n;x+=x&-x)
for(int j=y;j<=n;j+=j&-j) c[x][j]+=val;
}
inline int query(int x,int y)//请不要在意这个鬼畜的二维树状数组
{
int ans=0;
for(;x;x-=x&-x)
for(int j=y;j;j-=j&-j) ans+=c[x][j];
return ans;
}
inline void rev(int x1,int y1,int x2,int y2)
{
add(x1,y1,1),add(x1,y2+1,-1),add(x2+1,y1,-1),add(x2+1,y2+1,1);
}
int main()
{
int t,q;
t=read();
while(t--)
{
memset(c,0,sizeof(c));
n=read();q=read();
char op[2];
for(int i=1;i<=q;i++){
scanf("%s",op);
if(op[0]=='C'){
int x1,y1,x2,y2;
x1=read(),y1=read();
x2=read(),y2=read();
rev(x1,y1,x2,y2);
}
else{
int x,y;
x=read(),y=read();
printf("%d
",query(x,y)%2);
}
}
cout<<endl;
}
return 0;
}