POJ 2155 Matrix【二维树状数组】

题意：给出两种操作，C是给出一个矩形的左上角和左下角的下标，把这个矩形里面的0变成1,1变成0，Q是询问某个点的值

看这篇论文讲得很清楚

http://wenku.baidu.com/view/1e51750abb68a98271fefaa8

自己看的时候，把每个点对应覆盖哪些区域画出来，再结合论文里面的，好理解一些

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=1005;
17 
18 int n;
19 int c[maxn][maxn];
20 
21 int lowbit(int x){ return x & (-x);}
22 
23 int sum(int x,int y){
24     int ret=0,y1;
25     while(x>0){
26         y1=y;
27         while(y1>0){
28             ret+=c[x][y1];y1-=lowbit(y1);
29         }
30         x-=lowbit(x);
31     }
32     return ret;
33 }
34 
35 void add(int x,int y,int d){
36     int y1;
37     while(x<=n){
38         y1=y;
39         while(y1<=n){
40             c[x][y1]+=d;y1+=lowbit(y1);
41         }
42         x+=lowbit(x);
43     }
44 }
45 
46 int main(){
47     int T;
48     scanf("%d",&T);
49     while(T--){
50         int m;
51         memset(c,0,sizeof(c));
52         scanf("%d%d%*c",&n,&m);
53         while(m--){
54             char ch;
55             scanf("%c",&ch);
56             if(ch == 'C'){
57                 int x1,y1,x2,y2;
58                 scanf("%d%d",&x1,&y1);
59                 scanf("%d%d%*c",&x2,&y2);
60                 add(x1,y1,1);
61                 add(x1,y2+1,-1);
62                 add(x2+1,y1,-1);
63                 add(x2+1,y2+1,1);
64             }
65             else {
66                 int l,r;
67                 scanf("%d%d%*c",&l,&r);
68                 int ans;
69                 ans=sum(l,r);
70                 printf("%d
",ans%2);    
71             }
72         }    
73         if(T>=1) puts("");
74     }
75     return 0;
76 }

View Code

POJ 2155 Matrix【 二维树状数组 】

POJ 2155 Matrix【二维树状数组】