poj 2155 Matrix (二维树状数组)

       这里我用了二维的线树状数组，一维树状数组可以解决区间更新和点查询的问题，这里只需要加一维就可以了，代码比较好写，不过开始犯了很多低级的错误。

//============================================================================
// Name        : 2012083101.cpp
// Author      : xindoo
// Version     :
// Copyright   : Your copyright notice
// Description : poj 2155
// Data        : 2013-08-29-17.06
//============================================================================

#include <stdio.h>
#include <string.h>
const int maxn = 1004;
int xy[maxn][maxn];
int n;

inline int lowbit(int x)
{
    return x&-x;
}

void update(int x, int y, int v)
{
	int t = y;
    while (x <= n)
    {
    	y = t;
        while (y <= n)
        {
            xy[x][y] += v;
            y += lowbit(y);
        }
        x += lowbit(x);
    }
}

int getsum(int x, int y)
{
    int sum = 0;
    int t = y;
    while (x)
    {
    	y = t;
        while (y)
        {
            sum += xy[x][y];
            y -= lowbit(y);
        }
        x -= lowbit(x);
    }
    return sum;
}

int main()
{
    int q, kase;
    char op;
    int x1, x2, y1, y2;
    scanf("%d", &kase);
    while (kase--)
    {
        scanf("%d %d", &n, &q);
        memset(xy, 0, sizeof(xy));
        while (q--)
        {
            getchar();
            scanf("%c", &op);
            if (op == 'Q')
            {
                scanf("%d %d", &x1, &y1);
                int t = getsum(x1, y1);
                if (t&1)
                    printf("%d\n", 1);
                else
                    printf("%d\n", 0);
            }
            else
            {
                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);
            }
        }
        if (kase)
            puts("");
    }
    return 0;
}