poj2155

题目大意：给定一个n*n的矩阵，每个位置为0或1,初始全为0,

然后给定m个操作，每个操作修改或者询问

修改的话就是修改 x1,y1-->x2,y2的小矩阵的值，0改为1, 1改为0

询问的话就是询问 x，y位置是0或者1.

思路：很明显这题只涉及到奇偶操作，

对于一个点x，y，我们用0,0-->x,y的矩阵的和的奇偶性代表其奇偶性

这样，每次操作我们只要保证x1,y1-->x2,y2内的点改变奇偶性，其他点不改变奇偶性就可以了

所以我们只要改变矩阵四个角的奇偶性就行了。（画个图模拟下就很明白了）

这样其他就是求和更改的问题了，正好是树状数组的强项了

code：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <map>
 8 #include <set>
 9 #define MXN 1002
10 using namespace std;
11 
12 int  T, n, m, x1, y_1, x2, y2;
13 int sum[1010][1010];
14 
15 int lowbit(int t){ return t & (-t); }
16 
17 int getsum(int x, int y){
18     int ret = 0;
19     for (int i = x; i > 0; i -= lowbit(i))
20         for (int j = y; j > 0; j -= lowbit(j))
21             ret +=  sum[i][j];
22     return ret;
23 
24 }
25 
26 void updata(int x, int y, int data){
27     for (int i = x; i < MXN; i += lowbit(i))
28         for (int j = y; j < MXN; j += lowbit(j))
29             sum[i][j] += data;
30 
31 }
32 
33 
34 void solve(){
35      memset(sum, 0, sizeof(sum));
36      scanf("%d%d", &n , &m);
37      char c;
38      scanf("%c", &c);
39      for (int i = 1; i <= m; ++i){
40           scanf("%c", &c);
41           if (c == 'C'){
42                scanf("%d%d%d%d", &x1, &y_1, &x2, &y2);
43                updata(x1, y_1, 1);
44                updata(x2 + 1,y_1, 1 );
45                updata(x1, y2 + 1, 1);
46                updata(x2 + 1, y2 + 1, 1);
47           } else {
48                     scanf("%d%d", &x1, &y_1);
49                     printf("%d\n", getsum(x1, y_1) % 2);
50                  }
51           scanf("%c", &c);
52      }
53 }
54 
55 int main(){
56     freopen("poj2155.in", "r", stdin);
57     freopen("poj2155.out","w", stdout);
58     scanf("%d", &T);
59     for (int i = 0; i < T; ++ i){
60         solve();
61         if (i < T-1) printf("\n");
62     }
63     fclose(stdin); fclose(stdout);
64 }