poj-2155 Matrix

[题目链接]

思路：很详细的 二维数组讲解+本题 题解，orz~

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max_n=1e3+10;

int t,n,q;
int c[Max_n][Max_n];

int lowbit(int k){
    return k&-k;
}

void update(int x,int y,int val){
    int f=y;
    while(x>0){
        y=f;
        while(y>0){
            c[x][y]+=val;
            y-=lowbit(y);
        }
        x-=lowbit(x);
    }
}

int query(int x,int y){
    int f=y,ans=0;
    while(x<=n){
        y=f;
        while(y<=n){
            ans+=c[x][y];
            y+=lowbit(y);
        }
        x+=lowbit(x);
    }
    return ans;
}

int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&q);
        memset(c,0,sizeof(c));
        char s[10];
        int x1,x2,y1,y2;
        while(q--){
            scanf("%s",s);
            if(s[0]=='C'){
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                update(x2,y2,1);
                update(x2,y1-1,-1);
                update(x1-1,y2,-1);
                update(x1-1,y1-1,1);

//              for(int i=1;i<=n;i++){
//                  for(int j=1;j<=n;j++){
//                      cout<<c[i][j]<<' ';
//                  } 
//                  cout<<endl;
//              }
            }
            else{
                scanf("%d%d",&x1,&y1);
                printf("%d\n",query(x1,y1)%2);
            }
        }
        printf("\n"); 
    }
    return 0;
}