poj 2155- Matrix (树状数组，二维，更新区间，查询单点)

  1/*************************************************************************
  2	> File Name: code/poj/2155.cpp
  3	> Author: 111qqz
  4	> Email: rkz2013@126.com 
  5	> Created Time: 2015年08月07日 星期五 00时42分38秒
  6 ************************************************************************/
  7
  8#include<iostream>
  9#include<iomanip>
 10#include<cstdio>
 11#include<algorithm>
 12#include<cmath>
 13#include<cstring>
 14#include<string>
 15#include<map>
 16#include<set>
 17#include<queue>
 18#include<vector>
 19#include<stack>
 20#define y0 abc111qqz
 21#define y1 hust111qqz
 22#define yn hez111qqz
 23#define j1 cute111qqz
 24#define tm crazy111qqz
 25#define lr dying111qqz
 26using namespace std;
 27#define REP(i, n) for (int i=0;i<int(n);++i)  
 28typedef long long LL;
 29typedef unsigned long long ULL;
 30const int inf = 0x7fffffff;
 31const int N=1E3+7;
 32int c[N][N];
 33int n,m,x1,x2,y1,y2,x,y,t;
 34
 35int lowbit ( int x)
 36{
 37    return x&(-x);
 38}
 39void update ( int x,int y ,int delta)
 40{
 41    for ( int i = x ; i  <= n ; i = i + lowbit(i))
 42    {
 43	for ( int j = y; j <= n ; j = j + lowbit(j))
 44	{
 45	    c[i][j] = c[i][j] + delta;
 46	}
 47    }
 48}
 49int sum ( int x,int y)
 50{
 51    int res  = 0;
 52    for ( int i = x; i >= 1 ; i = i - lowbit (i))
 53    {
 54	for ( int j = y ; j >= 1 ; j = j - lowbit (j))
 55	{
 56
 57	    res  = res + c[i][j];
 58	}
 59    }
 60    return res;
 61}
 62int main()
 63{
 64    int T;
 65    cin>>T;
 66    while (T--)
 67    {
 68	memset(c,0,sizeof(c));
 69	scanf("%d %d",&n,&t);
 70	for ( int i = 1; i <=  t;  i ++ )
 71	{
 72	    char cmd;
 73	    cin>>cmd;
 74	    if (cmd=='C')
 75	    {
 76		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
 77//		cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl;
 78		update (x1,y1,1);
 79		update (x2+1,y1,1);
 80		update (x1,y2+1,1);
 81		update (x2+1,y2+1,1);
 82//		cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl;
 83	    }
 84	    else
 85	    {
 86		scanf("%d %d",&x,&y);
 87		int tmp;
 88//		cout<<"sum(x)(y):"<<sum(x,y)<<endl;
 89//	    	cout<<"sum(x-1,y-1):"<<sum(x-1,y-1)<<endl;
 90//		cout<<"sum(x-1,y):"<<sum(x-1,y)<<endl;
 91//		cout<<"sum(x,y-1):"<<sum(x,y-1)<<endl;
 92		tmp =sum(x,y)+sum(x-1,y-1)-sum(x-1,y)-sum(x,y-1);
 93//		cout<<"tmp:"<<tmp<<endl;
 94		if (sum(x,y)%2==0)
 95		    cout<<0<<endl;
 96		else cout<<1<<endl;
 97	    }
 98//	    cout<<"*****************"<<endl;
 99//	    for ( int ii = 1 ; ii <= n ; ii++)
100//	    {
101//		for ( int jj = 1 ; jj <= n ; jj++ )
102//		{
103//		    cout<<c[ii][jj]<<" ";
104//		}
105//		cout<<endl;
106//	    }
107//	    cout<<"*************************"<<endl;
108//
109	}
110	cout<<endl;
111    }
112
113	return 0;
114}