[POJ2155]Matrix（二维树状数组）

题目：http://poj.org/problem?id=2155

中文题意：

　　给你一个初始全部为0的n*n矩阵，有如下操作

　　　　1、C x1 y1 x2 y2 把矩形(x1,y1,x2,y2)上的数全部取反，1->0,0->1

　　　　2、Q x y 求n*n矩阵的（x,y)位置上的数

题解；

　　先看简单的：

　　　　给你一个初始全为0的长度为n的序列，有如下操作

　　　　　　1、C x y 把序列x到y位取反1->0,0->1

　　　　　　2、Q x 求序列第x位的数

　　　　做法很简单，设计一个数组a[]，a[1..i]的和表示第i位数的值，对于C把第x位和第y+1位全部加上1，对于Q只要求出a[1..x]的和表示第x位置上的数，判断下　　　　　　　　奇偶就行了。如何快速处理呢，问题是对一个序列进行修改一个点并求出前缀和，很明显是标准的树状数组操作

　　那么此题很容易发现就是上面那个一维的推广

　　　　设计一个数组a[][]，a[1..i][1..j]的和表示(i,j)位置上的数，对于C把(x1,y1),(x1,y2+1),(x2+1,y1),(x2+1,y2+1)4个位置的数加上1，对于Q求出a[1..i]　　 [1...j]的和，判断奇偶就行了。如何快速实现？修改单点+询问前缀矩阵和————>二维树状数组

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

View Code

刷难题无力只能刷水了……