POJ 2155 二维树状数组

《浅谈信息学中的“0”和“1”》这篇文章给出了该题目的二维树状数组做法。因为矩阵只含0和1，所以可以采取记录每个元素被置换的次数来获得该元素最后的状态。每次置换只需让端点(x1,y1),(x1,y2+1),(x2+1,y1),(x2+1,y2+1)加一。查询的时候利用维护的树状数组，得到元素(x,y)的置换次数判断其奇偶即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define lowbit(x) (x&(-x))
 4 int tree[1001][1001];
 5 int s;
 6 void add(int x,int y,int num)
 7 {
 8     for(int i=x;i<=s;i+=lowbit(i))
 9         for(int j=y;j<=s;j+=lowbit(j))
10             tree[i][j]+=num;
11 }
12 int read(int x,int y)
13 {
14     int num=0;
15     for(int i=x;i>0;i-=lowbit(i))
16         for(int j=y;j>0;j-=lowbit(j))
17             num+=tree[i][j];
18     return num;
19 }
20 int main()
21 {
22     int x;
23     scanf("%d",&x);
24     for(int i=0;i<x;i++)
25     {
26         int t,x1,x2,y1,y2;
27         char cmd;
28         memset(tree,0,sizeof(tree));
29         scanf("%d%d",&s,&t);
30         getchar();
31         for(int j=0;j<t;j++)
32         {
33             scanf("%c",&cmd);
34             if(cmd=='C')
35             {
36                 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
37                 getchar();
38                 add(x1,y1,1);
39                 add(x2+1,y2+1,1);
40                 add(x1,y2+1,1);
41                 add(x2+1,y1,1);
42             }
43             if(cmd=='Q')
44             {
45                 scanf("%d%d",&x1,&y1);
46                 getchar();
47                 printf("%d\n",read(x1,y1)&1);
48             }
49         }
50         printf("\n");
51     }
52 }