https://vjudge.net/problem/POJ-2155 给定一个矩阵，初始化都为0 两种操作 1 给定区间 左上角和右下角，将区间内坐标（闭区间） 取反操作 2 查询 某单点。 没有想到这样搞，很6，取反的操作、（摘自大佬的照片） http://blog.csdn.net/zxy_snow/article/details/6264135 这个 每次依据四个点。（注意右下角那个x,y要加1，这样就不会把边界加进去。另外俩也是） 2 为什么判断他们之间的操作，需要求 区间和（1，1-x,y）就可以呢qwq （摘自《浅谈信息学竞赛中的“0”和“1”》） http://blog.csdn.net/libin56842/article/details/46620445
当 在6时，计算两次，会抵消。8也是，9是计算4次抵消（和上面那个更新的操作好像，得出的结论就是该点的左上角的任何操作都不会对该点产生影响。该点会出现在 4,6,89，qwq）唯一产生影响的地方就是5，即直接的改变过该点的地方，而这，正好就是我们想要的qwq
#include <iostream> #include <stdio.h> #include <string.h> #include <string> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h> #include <bitset> #include <list> #include <algorithm> #include <climits> using namespace std; #define lowbit(x) (x&-x) const int mod = 1e9+7; /* 树状数组 区间求值。求得是 前缀和。 1 开始没有理解他更新的位置。这样操作是为了让边界也只进行 1 次更新，否则的话，边界就会进行4次更新。 2 查询单点也行了，（单点查询是为了干啥） */ int m,n; int bit[1005][1005]; void add(int a,int b){ for(int i=a;i<=m;i+=lowbit(i)) for(int j=b;j<=m;j+=lowbit(j)){ bit[i][j]++; }//区间修改。 } int query(int a,int b){ int sum=0; for(int i=a;i>=1;i-=lowbit(i)) for(int j=b;j>=1;j-=lowbit(j)) sum+=bit[i][j]; return sum; //区间查询 } int main() { int t; char s; scanf("%d",&t); int a,b,c,d; while(t--){ memset(bit,0,sizeof(bit)); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++){ cin>>s; if(s=='C'){ scanf("%d%d%d%d",&a,&b,&c,&d); a++,b++,c++,d++; add(c,d);//右下测区域 add(a-1,b-1);//全部 add(a-1,d);//下侧 add(c,b-1);//右侧 } else { scanf("%d%d",&a,&b); printf("%d\n",query(a,b)%2); } } printf("\n"); } return 0; }