题目大意：原题链接
题意很简单，就不赘诉了。
解题思路：
使用二维树状数组，很裸的题。
二维的写起来也很方便，两重循环。
Add(int x,int y,int val)表示(x,y)-(n,n)矩形区域被修改val次(在传入参数时val=1)
如果是要修改(x1,y1)-(x2,y2)的矩形区域。
那么可以在(x1,y1)处加1，在(x2+1,y1)处加1，在(x1,y2+1)处加1，在(x2+1,y2+1)处加1，那么总共：
(x1,y1)-(x2,y2)矩形区域被修改1次，(x2+1,y1)-(n,n)矩形区域被修改2次；
(x1,y2+1)-(n,n)矩形区域被修改2次，(x2+1,y2+1)-(n,n)矩形区域被修改4次；
画个坐标图就知道了。而修改偶数次则回到初始状态，即为0；奇数次则变换一次，即为1。
Sum(int x,int y)表示由于(1,1)-(x,y)矩形区域内的点的改变导致点(x,y)被改变的次数求和，即：
点(x,y)被改变的总次数，而查询单点就是求和，再判断奇偶即可。
注意：真没想到cin,cout差别这么大，该题如果用cin,cout输入输出的话会超时。
#include<cstdio> #include<cstring> using namespace std; int n,T,m[1010][1010]; int lowbit(int x) { return x&(-x); } int Sum(int x,int y) { int res=0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) res+=m[i][j]; return res; } void Add(int x,int y,int val) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) m[i][j]+=val; } int main() { scanf("%d",&T); while(T--){ int q; scanf("%d%d",&n,&q); memset(m,0,sizeof(m)); char op[10]; int x,y,x1,y1,x2,y2; while(q--){ scanf("%s",op); if(op[0]==‘C‘){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); Add(x1,y1,1); Add(x2+1,y1,1); Add(x1,y2+1,1); Add(x2+1,y2+1,1); } else{ scanf("%d%d",&x,&y); if(Sum(x,y)%2==0) printf("0\n"); else printf("1\n"); } } if(T>0) printf("\n"); } }
原文：http://www.cnblogs.com/freinds/p/6422190.html