poj2155Matrix【二位树状数组】

大意：告诉你一个矩阵，初始值全部为0，有两种操作，1、告诉你x1，y1， x2， y2 把左上角到右下角的矩形的里面的值全部颠倒 1变0 0变1

第二种操作是查询某个点的值是0或1

分析：二维的标号法，对于每一个矩阵只要把它的四个角进行标记就可以了，最基本的思路跟理工门前的树是一样的

举个例子：

比如告诉你左上角（x1， y1）右下角（x2， y2）

那么对于这个矩形我们只要把（x1， y1），（x1 + 1， y2），（x2 + 1， y1），（x2 + 1， y2 + 1）标记上

那么对于每次查询的话该位置的值就是从该位置到（1， 1）这个矩阵之内的所有的数的和

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 1005;
 7 
 8 int lowbit(int x) {
 9     return x & ( - x );
10 }
11 
12 int c[maxn][maxn];
13 int n;
14 
15 void add(int i, int j, int value) {
16     int xx = j;
17     while(i <= n) {
18         j = xx;
19         while(j <= n) {
20             c[i][j] += value;
21             j += lowbit(j);
22         }
23         i += lowbit(i);
24     }
25 }
26 
27 int Sum(int i, int j) {
28     int xx = j;
29     int sum = 0;
30     while(i > 0) {
31         j = xx;
32         while(j > 0) {
33             sum += c[i][j];
34             j -= lowbit(j);
35         }
36         i -= lowbit(i);
37     }
38     return sum;
39 }
40 
41 int main() {
42     int t;
43     int m;
44     char cc;
45     int x1, y1, x2, y2;
46     bool flag = false;
47     scanf("%d",&t);
48     while(t--) {
49         if(flag) puts("");
50         flag = true;
51         scanf("%d %d",&n, &m);
52         memset(c, 0, sizeof(c));
53         for(int i = 1; i <= m; i++) {
54             scanf("
%c %d %d", &cc, &x1, &y1);
55             if(cc == 'C') {
56                 scanf("%d %d",&x2, &y2);
57                 add(x1, y1, 1);
58                 add(x1, y2 + 1, 1);
59                 add(x2 + 1, y1, 1);
60                 add(x2 + 1, y2 + 1, 1);
61             } else {
62                 printf("%d
", Sum(x1, y1) % 2 );
63             }
64         }
65     }
66     return 0;
67 }
68

View Code