题意： 有一个n*n的矩阵，初始化全部为0。有2中操作； 1、给一个子矩阵，将这个子矩阵里面所有的0变成1，1变成0；2、询问某点的值
方法一：二维线段树
参考链接：
http://blog.csdn.net/xiamiwage/article/details/8030273
思路： 二维线段树，一维线段树的成段更新需要lazy。 引申到二维线段树应该需要一个lazy，一个sublazy，可是这里什么都不用。
奇妙之处在于这题的操作是异或，当某一段区间需要异或操作时候， 不必更新到它所有的叶子结点，可以像lazy那样父结点异或后就返回。
只要在查询时从根节点开始异或，而不是直接查叶子结点，这样相当于将lazy储存在父结点上。
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std;
const int maxn=;
int tree[maxn*][maxn*];
int n,t,sum;
/*
更新子线段树，tl、tr对应子矩阵的y1、y2，即要更新的范围。
rtx：母线段树(x轴)的节点，表示该子线段树属于母线段树的节点rtx
rt：子线段树的节点序号
L,R为子线段树节点rt的两端点
*/
void updatey(int rtx,int rt,int tl,int tr,int L,int R){
//一开始弄反了，写成L<=tl && tr<=R。。。
//要注意，应该是所在节点rt的区间在所要更新的节点范围里，更新节点rt的区间对应的值
if(tl<=L && R<=tr){
tree[rtx][rt]^=; //对属于更新范围里的子矩阵进行取反
return;
}
int mid=(L+R)>>;
//下面部分也可以换成注释掉的语句
if(tl<=mid)
updatey(rtx,rt<<,tl,tr,L,mid);
if(tr>mid)
updatey(rtx,rt<<|,tl,tr,mid+,R);
/*
if(tr<=mid)
updatey(rtx,rt<<1,tl,tr,L,mid);
else if(tl>mid)
updatey(rtx,rt<<1|1,tl,tr,mid+1,R);
else{
updatey(rtx,rt<<1,tl,mid,L,mid);
updatey(rtx,rt<<1|1,mid+1,tr,mid+1,R);
}
*/ }
/*
更新左上角(x1,y1)，右下角(xr,yr)的子矩阵区域
更新时，先在x轴找到对应[xl,xr]区间的点，再找按y轴找到对应[yl,yr]区间的节点
rt:母线段树的节点序号
L,R:rt节点的区间端点
*/
void updatex(int rt,int xl,int xr,int yl,int yr,int L,int R){
//一开始弄反了，写成L<=xl && xr<=R。。。
if(xl<=L && R<=xr){
updatey(rt,,yl,yr,,n);
return;
}
int mid=(L+R)>>;
//下面部分也可以换成注释掉的语句
if(xl<=mid)
updatex(rt<<,xl,xr,yl,yr,L,mid);
if(xr>mid)
updatex(rt<<|,xl,xr,yl,yr,mid+,R);
/*
if(xr<=mid)
updatex(rt<<1,xl,xr,yl,yr,L,mid);
else if(xl>mid)
updatex(rt<<1|1,xl,xr,yl,yr,mid+1,R);
else{
updatex(rt<<1,xl,mid,yl,yr,L,mid);
updatex(rt<<1|1,mid+1,xr,yl,yr,mid+1,R);
}
*/ }
/*
这里注意的是，是直到L!=R的时候，才停止查询，否则就要一直查询下去，直到查询到y所在的叶子节点
因为这里“异或”就相当于lazy标记，所以要获得最后的值，则必须遍历过y所在的所有子矩阵
rtx：母线段树(x轴)的节点，表示该子线段树属于母线段树的节点rtx
rt：子线段树的节点序号
L,R为子线段树节点rt的两端点
*/
void queryy(int rtx,int rt,int y,int L,int R){
sum^=tree[rtx][rt]; //这里注意：要先异或！
if(L!=R){
int mid=(L+R)>>;
if(y<=mid)
queryy(rtx,rt<<,y,L,mid);
else
queryy(rtx,rt<<|,y,mid+,R);
}
}
/*
这里注意的是，是直到L!=R的时候，才停止查询，否则就要一直查询下去，直到查询到点x所在的叶子节点
因为这里“异或”就相当于lazy标记，所以要获得(x,y)最后的值，则必须遍历过(x,y)点所在的所有子矩阵
rt：母线段树的节点序号
L,R为子线段树节点rt的两端点
x,y为所要查找的点的值
*/
void queryx(int rt,int x,int y,int L,int R){
queryy(rt,,y,,n);
//注意：当L<R的时候，还要继续往下查询，直到L=R=y。而不是到L<=Y<=R的时候就停止
if(L!=R){
int mid=(L+R)>>;
if(x<=mid)
queryx(rt<<,x,y,L,mid);
else
queryx(rt<<|,x,y,mid+,R);
}
}
int main()
{
int x,x1,x2,y1,y2;
char s[];
scanf("%d",&x);
while(x--){
memset(tree,,sizeof(tree));
scanf("%d%d",&n,&t);
for(int i=;i<=t;i++){
scanf("%s",s);
if(s[]=='C'){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
updatex(,x1,x2,y1,y2,,n);
}
else{
sum=; //查询的A(x,y)的值
scanf("%d%d",&x1,&y1);
queryx(,x1,y1,,n);
printf("%d\n",sum);
}
}
puts(" ");
}
return ;
}
方法二：二维树状数组
区间更新，单点查询
（修改一个区间的值，快速返回某一点处的值。）
树状数组有两种用途（以一维树状数组举例）：
1.单点更新，区间查询（即求和）
单点更新时，是往树根（即c[n]）拓展
而区间查询时，是往叶子节点（即c[1]）拓展
2.区间更新，单点查询
区间更新时，是往叶子节点（即c[1]）拓展
单点查询时，往树根（即c[n]）拓展
二维数组就是多了一层循环，其余一致
具体实现：
更新的时候，要更新四个矩阵，见下图，我采用的是法二。
每次查询时，统计该点被取反的次数，然后模2即为答案。
图片来自：http://blog.csdn.net/zxy_snow/article/details/6264135
即如果要对矩阵D中的元素取反，那么我先对ABCD四个矩阵操作一次（+1），再对矩阵AC和BC操作一次（-1），然后还要对矩阵C操作一次（+1）
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
const int maxn=;
int c[maxn][maxn];
int x,n,t; int lowbit(int x){
return x&(-x);
}
/*
原先一直WA，是因为直接用参数的i和j参与循环了
后来定义了变量x和y，就AC了。。。
后来仔细发现，每当外循环一次时，内循环就要从头开始。
而如果我直接用参数j参与循环，那么只有第一次外循环时，内循环执行。之后的外循环，内循环就再也不执行了。
真的是囧啊！！！
*/
void update(int i,int j,int v){
for(int x=i;x>=;x-=lowbit(x)){
for(int y=j;y>=;y-=lowbit(y))
c[x][y]+=v;
}
}
int sum(int i,int j){
int res=;
for(int x=i;x<=n;x+=lowbit(x)){
for(int y=j;y<=n;y+=lowbit(y))
res+=c[x][y];
}
return res;
}
int main()
{
char str[];
int x1,y1,x2,y2;
scanf("%d",&x);
bool flag=false;
while(x--){ if(flag)
puts("");
else
flag=true; scanf("%d%d",&n,&t);
memset(c,,sizeof(c));
while(t--){
scanf("%s",str);
if(str[]=='C'){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
update(x2,y2,); //矩阵ABCD
update(x1-,y2,-); //矩阵AC
update(x2,y1-,-); //矩阵BC
update(x1-,y1-,); //矩阵C
}
else{
scanf("%d%d",&x1,&y1);
int ans=sum(x1,y1);
if(ans%==)
printf("0\n");
else
printf("1\n");
}
}
}
return ;
}