poj 2155 Matrix

http://poj.org/problem?id=2155

题意：提供一个M*N的矩阵，其中每一个格子中的数不是1就是0，初始时每一个格子的值为0，我们可以修改这个矩阵中的数字，每次给出矩阵的左上角坐标(x1,y1)，以及右下角的坐标(x2,y2)，并且将矩阵中的数字全部取反（原来是1现在变成0，原来是0现在变成1）,还可以每次查询第x行第y列的格子中的数字是什么。

思路：用树状数组，每次插入，在(x1,y1),(x1,y2+1),(x2+1,y1),(x2+1,y2+1)格子内加1，查询的时候求出sum(x,y)就可以。证明参考 <<浅谈信息学竞赛中的““0”和“1”>>这篇论文，作者：武森。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 20000
using namespace std;

int x;
int n,t;
int x1,y1,x2,y2;
int c[1001][1001];

int low_bit(int x)
{
    return x&(-x);
}

void update(int x,int y,int m)
{
    while(x<=n)
    {
        int yy=y;
        while(yy<=n)
        {
            c[x][yy]+=m;
            yy+=low_bit(yy);
        }
        x+=low_bit(x);
    }
}

int sum(int x,int y)
{
    int sum1=0;
    while(x>=1)
    {
        int yy=y;
        while(yy>=1)
        {
            sum1+=c[x][yy];
            yy-=low_bit(yy);
        }
        x-=low_bit(x);
    }
    return sum1;
}

int main()
{
    scanf("%d",&x);
    while(x--)
    {
        memset(c,0,sizeof(c));
        scanf("%d%d",&n,&t);
        getchar();
        for(int i=1; i<=t; i++)
        {
            char ch;
            scanf("%c",&ch);
            if(ch=='C')
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                update(x1,y1,1);
                update(x1,y2+1,1);
                update(x2+1,y1,1);
                update(x2+1,y2+1,1);
            }
            else  if(ch=='Q')
            {
                scanf("%d%d",&x1,&y1);
                printf("%d
",sum(x1,y1)%2);
            }
            getchar();
        }
        if(x>0) printf("
");
    }
    return 0;
}