POJ 2155 Matrix

二维的树状数组，这题要逆向。
即最开始的点的是树状数组的终点。。。
View Code
 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 const int maxn = 1005;
 5 int ans[maxn][maxn],n;
 6 int lowbit(int x)
 7 {
 8     return x & (-x);
 9 }
10 
11 void mod(int x,int y,int c)
12 {
13     int i;
14     while(x>0)
15     {
16         i=y;
17         while(i>0)
18         {
19             ans[x][i]+=c;
20             i-=lowbit(i);
21         }
22         x-=lowbit(x);
23     }
24 }
25 int getSum(int x, int y)
26 {
27     int i,sum=0;
28     while(x<=n)
29     {
30         i=y;
31         while(i<=n)
32         {
33             sum+=ans[x][i];
34             i+=lowbit(i);
35         }
36         x+=lowbit(x);
37     }
38     return sum&1;
39 }
40 int main()
41 {
42     int t,k,x1,y1,x2,y2,f=0;
43     string s;
44     cin>>t;
45     while(t--)
46     {
47         if(f) cout<<endl;
48         f=1;
49         cin>>n>>k;
50         memset(ans,0,sizeof(ans));
51         while(k--)
52         {
53             cin>>s;
54             if(s=="C")
55             {
56                 cin>>x1>>y1>>x2>>y2;
57                 mod(x2,y2,1);
58                 mod(x1-1,y2,-1);
59                 mod(x2,y1-1,-1);
60                 mod(x1-1,y1-1,1);
61             }
62             else
63             {
64                 cin>>x1>>y1;
65                 cout<<getSum(x1,y1)<<endl;
66             }
67         }
68     }
69     return 0;
70 }