POJ 2155 Matrix（二维树状数组）

　　与以往不同的是,这个树状数组是二维的,仅此而已

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
int n,c[1100][1100];
int lowbit(int k)
{
    return k&(-k);
}
void add(int x,int y,int num)
{
    for(int i = x; i <= n; i += lowbit(i))
        for(int j = y; j <= n; j += lowbit(j))
            c[i][j] += num;

}
int cal(int x,int y)
{
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        for(int j = y; j >= 1; j -= lowbit(j))
            sum += c[i][j];
    return sum;
}
int  main()
{
    int x;
    scanf("%d",&x);
    while(x--)
    {
        int t;
        memset(c,0,sizeof(c));
        scanf("%d%d",&n,&t);
        char op;
        while(t--)
        {
            cin>>op;
            if(op == 'C')
            {
                int x1,y1,x2,y2;
                scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                x1++,x2++,y1++,y2++;
                add(x2,y2,1);
                add(x1-1,y1-1,1);
                add(x1-1,y2,1);
                add(x2,y1-1,1);
            }
            else
            {
                int x,y;
                scanf("%d%d",&x,&y);
                //++x,++y
                int ans = cal(x,y);// - cal(x-1,y-1) - cal(x-1,y) - cal(x,y-1);
                ans %= 2;
                printf("%d
",ans);
            }
        }
        puts("");
    }
    return 0;
}