POJ 2155 Matrix（樹狀數組+單點更新）

好多天沒幹活了，趕緊更新一篇。

題意：給定一矩陣，初始值均為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;
}