（树套树，二维树状数组，二维线段树）
Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].
Input
The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.
Output
For each querying output one line, which has an integer representing A[x, y].
There is a blank line between every two continuous test cases.
Sample Input
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
Sample Output
1
0
0
1
题目大意：
有一个n*n的矩形平面，里面每个点初始为0，有两种操作：
1.将左上角为（x1，y1），右下角为（x2，y2）的矩形区域中的每个点，把0变成1，把1变成0
2.查询点（x，y）当前的值
Sol: 根本思想，找一个点被哪些矩形覆盖，即它在哪些矩形中。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep(i,n) for(int i=0;i<n;++i)
#define mes(s,c) memset(s,c,sizeof(s))
const int maxn=1001;
using namespace std;
int sum[maxn<<2][maxn<<2];
int n,m;
int ans;
void Subbuild(int st,int l,int r,int rt)
//针对每一行，建立一个线段树
{
sum[st][rt]=0;
if(l==r) return ;
int m=(l+r)>>1;
Subbuild(st,lson);
Subbuild(st,rson);
}
void Build(int l,int r,int rt)
//建立整个线段树,一个矩形
{
Subbuild(rt,1,n,1);
if(l==r) return;
int m=(l+r)>>1;
Build(lson);
Build(rson);
}
void Subupdate(int L,int R,int st,int l,int r,int rt)
//st这个参数一直不变的，它对应x轴
//rt在调用时会发生变化，它对应y轴
{
if(L<=l&&r<=R)
{
sum[st][rt]^=1;
return ;
}
int m=(l+r)>>1;
if(L<=m)
Subupdate(L,R,st,lson);
if(m<R)
Subupdate(L,R,st,rson);
}
void Update(int x1,int y1,int x2,int y2,int l,int r,int rt)
//[x1,y1]和[x2,y2]分别代表查询区域的左上角和右下解
//[l,r]代表线段上x轴的范围， rt代表对应的根结号
//在更新矩形的时候，先根据x1,x2找它们在矩形的哪个行号区域
{
if(x1<=l&&r<=x2)
//找到了对应的x轴区间，于是在y轴上进行修改
{
Subupdate(y1,y2,rt,1,n,1);
return ;
}
int m=(l+r)>>1;
if(x1<=m) // 如果落在矩形的上半部
Update(x1,y1,x2,y2,lson);
if(m<x2)
Update(x1,y1,x2,y2,rson);
}
void Subquery(int L,int R,int st,int l,int r,int rt)
//[L,R]要查询的区域，根据它们找其在y轴的左边还是右边
//st代表是属于x轴上哪个点
//[l,r]代表当前y轴上的区域
//rt代表对应[l,r]区轴上根结点编号
{
ans^=sum[st][rt];
if(l==r) return;
int m=(l+r)>>1;
if(R<=m) //落在y轴的左边
Subquery(L,R,st,lson);
else //落在y轴的右边
Subquery(L,R,st,rson);
}
void Query(int L,int R,int l,int r,int rt)
//初始调用为Query(x,y,1,n,1);
//[L,R]代表要查询的点
//[l,r]代表x轴上的区域，rt是其根
{
Subquery(L,R,rt,1,n,1);
//要查询的点[L,R]必然是落在当前根rt(描述所有x轴)
//[1,n]代表所有列，1是其根
//也就是说当前点一定是落在整个矩形中的
//如果它是上半部的某个点，也必然是落在整个上半部中的
//就这样递归找下去，看这个点落在多少个矩形中
if(l==r) return ;
int m=(l+r)>>1;
if(L<=m) //落在矩形的上半部
Query(L,R,lson);
else //落在矩形的下半部
Query(L,R,rson);
}
int main()
{
int T;
cin>>T;
while(T--){
scanf("%d%d",&n,&m);
Build(1,n,1);
char op[10];
int x1,y1,x2,y2,x,y;
while(m--){
scanf("%s",op);
if(op[0]=='C')
//修改操作
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
Update(x1,y1,x2,y2,1,n,1);
}
else
{
ans=0;
scanf("%d%d",&x,&y);
Query(x,y,1,n,1);
printf("%d
",ans);
}
}
if(T) puts(" ");
}
return 0;
}
//注意这题是矩形修改，然后单点询问，所以要看这个点被哪些矩形包括了.
#include <stdio.h>
#include <string.h>
#define MAXN 1005
#define mem(a) memset(a, 0, sizeof(a))
bool tree[MAXN<<2][MAXN<<2];
int X, N, T;
int num, X1, X2, Y1, Y2;
char ch[10];
void updatey(int yl,int yr,int xp,int yp)
{
if(Y1<=yl && yr<=Y2)
{
tree[xp][yp]=!tree[xp][yp];
return;
}
int mid=(yl+yr)>>1;
if(Y1<=mid)
updatey(yl,mid,xp,yp<<1);
if(Y2>mid )
updatey(mid+1,yr,xp,yp<<1|1);
}
void updatex(int xl,int xr,int xp)
{
if(X1<=xl && xr<=X2)//目前所在区间在所要更新区间内部
{
updatey(1,N,xp,1);
return;
}
int mid=(xl+xr)>>1;
if(X1<=mid)
updatex(xl,mid,xp<<1);
if(X2>mid)
updatex(mid+1,xr,xp<<1|1);
}
void queryy(int yl,int yr,int xp,int yp)
{
num+=tree[xp][yp];//xp代表xp轴即外面那棵树，yp代表内层那棵树
if(yl==yr)
return;
int mid=(yl+yr)>>1;
if(Y1<=mid)
queryy(yl,mid,xp,yp<<1);
else
queryy(mid+1,yr,xp,yp<<1|1);
}
void queryx(int xl,int xr,int xp)
{
queryy(1,N,xp,1);
//对于xp这棵x轴上的线段线段树，查询y这个线段树上的第1个点，其管辖范围是1,N
if(xl==xr)
return;
int mid=(xl+xr)>>1;
if(X1<=mid) //看目标点落在整个矩形的上半部分还是下半部分
queryx(xl,mid,xp<<1);
else
queryx(mid+1,xr,xp<<1|1);
}
int main()
{
while(~scanf("%d", &X))
while(X--)
{
mem(tree);
scanf("%d %d%*c", &N,&T);
for(int i=0;i<T;i++)
{
scanf("%s%d%d",ch,&X1,&Y1);
if(ch[0]=='Q')
//统计(x1,y1)这个点被改了多少次，
//由于我们在修改时矩形内所有点变换，所以要看哪些矩形是包含当前这个点的
{
num=0;
queryx(1,N,1);
//1和N代表是x轴上，1代表外层线段树上第一个点,它管辖所有的点
printf("%d
",num%2);}
else
{
scanf("%d%d",&X2,&Y2);
//修改操作[X1,Y1]是左上角,[X2,Y2]是右下角
updatex(1,N,1);
}
}
if(X) printf("
");
}
return 0;
}