1

2 10

C 2 1 2 2

Q 2 2

C 2 1 2 1

Q 1 1

C 1 1 2 1

C 1 2 1 2

C 1 1 2 2

Q 1 1

C 1 1 2 1

Q 2 1

1

0

0

1

题意：给出矩阵左上角和右下角坐标，矩阵里的元素 1变0 ，0 变1，然后给出询问，问某个点是多少。

题解：纠结了好久，看了这篇博客后秒懂http://blog.sina.com.cn/s/blog_626489680100k75p.html

先举个一维的样例：你要使区间[x,y]所有加上一个值v,结合树状数组的功能，能够类似扫气球那样，在x处加v, y+1处减1

这样假设你要求x处的值，就转换成求[1,x]的和了，比如 ：一个n=6的数组，一開始为0  0  0   0  0  0

在[2,4]加上2后变成   0   2   0   0   -2    0  这样前缀和 sum[1]=0;sum[2]=2;sum[3]=2;sum[4]=2;sum[5]=0;sum[6]=0;

依次代表了每一个数的值。

二维的也一样，由于二维树状数组的getsum(int x,int y)函数是求矩阵（1,1）~(x,y)的值得和。也就类似于前缀和。原理和一维的一样

仅仅只是线操作改成了平面操作。自己能够画个图感受下。

即：

add(x,y,1);

                add(x,y1+1,-1);

                add(x1+1,y,-1);

                add(x1+1,y1+1,1);

然后查询单点就是求和了。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#define N 1040

#define ll long long

using namespace std;

int n;

int bit[N][N];

int sum(int i,int j) {

    int s=0;

    while(i>0) {

        int jj=j;

        while(jj>0) {

            s+=bit[i][jj];

            jj-=jj&-jj;

        }

        i-=i&-i;

    }

    return s;

}

void add(int i,int j,int x) {

    while(i<=n) {

        int jj=j;

        while(jj<=n) {

            bit[i][jj]+=x;

            jj+=jj&-jj;

        }

        i+=i&-i;

    }

}

int main() {

    freopen("test.in","r",stdin);

    int t;

    cin>>t;

    while(t--) {

        int q;

        scanf("%d%d ",&n,&q);

        memset(bit,0,sizeof bit);

        char c;

        int x,y,x1,y1;

        while(q--) {

            scanf("%c",&c);

            if(c=='C') {

                scanf("%d%d%d%d",&x,&y,&x1,&y1);

                add(x,y,1);

                add(x,y1+1,-1);

                add(x1+1,y,-1);

                add(x1+1,y1+1,1);//重叠的部分加上

            } else {

                scanf("%d%d",&x,&y);

                printf("%d\n",sum(x,y)%2);

            }

            getchar();

        }

        if(t)printf("\n");

    }

    return 0;

}