学步园

好多天没干活了，赶紧更新一篇。

题意：给定一矩阵，初始值均为0。现有两种操作：1.将以(x1, y1)为左上角，(x2, y2)为右下角的矩阵中的所有0变为1，所有1变为0；2.查询位置(x, y)是0还是1。

要点:

1.sum(i)是求第i位的前缀和，add(i)是更新位置i的单点值。

2.翻转两次相当于没有翻转。

假设x为位置i的翻转次数，那么可以将x看做一个集合，x = { x + 2 * k | k =  整数 }【格式不是很标准，意会一下】；

令i的前缀和为位置i的翻转次数的集合中的一个元素。

假设要给绿色部分都反转，那么绿色部分里面的每个点的前缀和都要加一个奇数，比如1；

可给绿色部分的左上角加一，这样绿色部分的每个点求前缀和的时候都会加一了；

但是这样紫色部分和肤色部分还有粉红色部分也加了一；

所以还要加，把三个部分加成偶数；

于是加绿色右上角，绿色左下角，绿色右下角都加1；

这样肤色和粉色部分的前缀和都加了2，紫色部分是加了4，消除了绿色左上角加一的影响。

剩下的就是二维树状数组乱搞了。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAXN 1005

int s[MAXN][MAXN];
char o[4];
int x1, x2, y1, y2, n, q, ans;

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

int sum(int i, int j)
{
    int ret = 0;
    while(i > 0)
    {
        int tj = j;
        while(tj > 0)
        {
            ret += s[i][tj];
            tj -= lowbit(tj);
        }
        i -= lowbit(i);
    }
    return ret;
}

void add(int i, int j)
{
    while(i <= n)
    {
        int tj = j;
        while(tj <= n)
        {
            s[i][tj]++;
            tj += lowbit(tj);
        }
        i += lowbit(i);
    }
}

int main()
{
//    freopen("B.in", "r", stdin);

    int t; scanf("%d", &t);
    bool flag = false;
    while(t--)
    {
        if(flag) puts("");
        if(!flag) flag = true;

        scanf("%d%d", &n, &q);
        memset(s, 0, sizeof(s));

        while(q--)
        {
            scanf("%s", o);
            if(o[0] == 'C')
            {
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                add(x1, y1);
                add(x1, y2 + 1);
                add(x2 + 1, y1);
                add(x2 + 1, y2 + 1);

            }
            if(o[0] == 'Q')
            {
                scanf("%d%d", &x1, &y1);
                ans = sum(x1, y1);// - sum(x1, y1 - 1) - sum(x1 - 1, y1) + sum(x1 - 1, y1 - 1);
                printf("%d\n", ans & 1);
            }
        }
    }
    return 0;
}