学步园

题意：对于一个N*N的矩阵（2 <= N <= 1000），其中的元素初始为0，执行2种操作，一：C x1 y1 x2 y2——>对矩阵(x1, y1, x2, y)的所有元素求反（0——>1, 1——>0），二：Q x y——>问元素(x, y)的值。

题目链接：http://poj.org/problem?id=2155

——>>好题，好题。。。一般我们都能想到，只要知道位置(x, y)被翻的次数就行。。。对于一个二维区间的修改，我们可以只修改其左闭右开区间的端点。

原理：若其中修改为区间[x1, x2]，其左闭右开区间为[x1, x2+1)，只在x1和x2+1的位置执行翻转，那么，如果询问x1之前的，本来就没什么修改；如果询问[x1, x2]的，修改了一次，正确；如果询问[x2+1, +oo)的，修改为2次，偶数次修改值不变，正确。

——>>所以，这里只要修改4个点的值，(x1, y1)（修改）, (x1, y2+1)（把值变回去）, (x2+1, y1)（把值变回去）, (x2+1, y2+1)（把值变回去）。。。#^_^。。。

。。。一不小心，让那个空行要求。。。PE了一次。。。T_T～

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 1000 + 10;

int N;
int c[maxn][maxn];

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

void add(int x1, int y1, int x2, int y2) {
    for(int i = x1; i <= N; i += lowerbit(i))
        for(int j = y1; j <= N; j += lowerbit(j))
            c[i][j]++;
    for(int i = x1; i <= N; i += lowerbit(i))
        for(int j = y2+1; j <= N; j += lowerbit(j))
            c[i][j]++;
    for(int i = x2+1; i <= N; i += lowerbit(i))
        for(int j = y1; j <= N; j += lowerbit(j))
            c[i][j]++;
    for(int i = x2+1; i <= N; i += lowerbit(i))
        for(int j = y2+1; j <= N; j += lowerbit(j))
            c[i][j]++;
}

int query(int x, int y) {
    int ret = 0;
    for(int i = x; i > 0; i -= lowerbit(i))
        for(int j = y; j > 0; j -= lowerbit(j))
            ret += c[i][j];
    return ret % 2;
}

int main()
{
    int X, T, x1, y1, x2, y2;
    char op;
    scanf("%d", &X);
    while(X--) {
        scanf("%d%d", &N, &T);
        memset(c, 0, sizeof(c));
        while(T--) {
            getchar();
            op = getchar();
            if(op == 'C') {
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                add(x1, y1, x2, y2);
            }
            else {
                scanf("%d%d", &x1, &y1);
                printf("%d\n", query(x1, y1));
            }
        }
        if(X) puts("");
    }
    return 0;
}