题意 : 给出一个N*N的矩阵, 矩阵只有可能包含0或1, 一开始则全部是0。对于矩阵可以进行两种操作, 第一种是输入 C x1 y1 x2 y2 表示, 对以(x1, y1)为左上角, 以(x2, y2)为右下角构成的矩形区域内的数全部进行取反操作, 即0变1、1变0。第二种是Q X Y, 表示查询现在这个矩阵的(X, Y)点到底是0还是1。总共有T次操作, 对于C操作进行相应的修改, 对于Q操作要对应输出！
分析 : 据说是楼教主出的题, 自己确实想不出什么高效的办法, 参考网上的题解, 才得知解题思想源自一篇国家队论文, 说简单一点就是对于题目要求的C操作, 实际上只要更新这个小矩形区域的四个点即可, 也就是不必全部照样更新。在Q操作查询时候也只要进行二维的树状数组进行(1,1)到(X, Y)点的矩形区域求和, 然后将求和结果%2, 如果得1即这个点被进行了奇数次操作, 所以应为1, 得0则反之。至于为什么或者如何做, 论文讲的很清楚, 请百度: 《浅谈信息学竞赛中的“0”和“1”》
瞎想 : 很值得借鉴的是对于是否是0或1的判断, 被转化成判断了对这个点操作次数的奇偶。还有对于区间的修改, 对于一维只进行两点的起始标记, 二维则进行四个点的起始标记, 这个也是厉害！
#include<stdio.h>
#include<string.h>
#define lowbit(i) (i&(-i))
;
int c[maxn][maxn], n;
inline void add(int row, int col)
{
for(int i=row; i<=n; i+=lowbit(i)){
for(int j=col; j<=n; j+=lowbit(j)){
c[i][j]++;
}
}
}
int sum(int row, int col)
{
;
; i-=lowbit(i)){
; j-=lowbit(j)){
ans += c[i][j];
}
}
return ans;
}
inline void initialize(int k)
{
; i<=k; i++){
memset(c[i], , sizeof(c[i]));
}
}
int main(void)
{
int nCase;
scanf("%d", &nCase);
while(nCase--){
scanf("%d", &n);
initialize(n);
int num;
scanf("%d", &num);
while(num--){
char command;
scanf(" %c", &command);
if(command=='C'){
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
add(x1, y1);
add(x2+, y1);
add(x1, y2+);
add(x2+, y2+);
}else{
int x, y;
scanf("%d%d", &x, &y);
int SUM = sum(x, y);
printf();//&1和%2好像效率一样！
}
}
puts("");//注意这里, 用例之间要空个行, 避免PE
}
;
}