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

 1#include<iostream>
 2#include<iomanip>
 3#include<cstdio>
 4#include<algorithm>
 5#include<cmath>
 6#include<cstring>
 7#include<string>
 8#include<map>
 9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)  
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=1E3+7;
25int c[N][N];
26int n,m,x1,x2,y1,y2,x,y,t;

 1int lowbit ( int x)
 2{
 3    return x&(-x);
 4}
 5void update ( int x,int y ,int delta)
 6{
 7    for ( int i = x ; i  <= n ; i = i + lowbit(i))
 8    {
 9	for ( int j = y; j <= n ; j = j + lowbit(j))
10	{
11	    c[i][j] = c[i][j] + delta;
12	}
13    }
14}
15int sum ( int x,int y)
16{
17    int res  = 0;
18    for ( int i = x; i >= 1 ; i = i - lowbit (i))
19    {
20	for ( int j = y ; j >= 1 ; j = j - lowbit (j))
21	{

 1	    res  = res + c[i][j];
 2	}
 3    }
 4    return res;
 5}
 6int main()
 7{
 8    int T;
 9    cin>>T;
10    while (T--)
11    {
12	memset(c,0,sizeof(c));
13	scanf("%d %d",&n,&t);
14	for ( int i = 1; i <=  t;  i ++ )
15	{
16	    char cmd;
17	    cin>>cmd;
18	    if (cmd=='C')
19	    {
20		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
21//		cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl;
22		update (x1,y1,1);
23		update (x2+1,y1,1);
24		update (x1,y2+1,1);
25		update (x2+1,y2+1,1);
26//		cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl;
27	    }
28	    else
29	    {
30		scanf("%d %d",&x,&y);
31		int tmp;
32//		cout<<"sum(x)(y):"<<sum(x,y)<<endl;
33//	    	cout<<"sum(x-1,y-1):"<<sum(x-1,y-1)<<endl;
34//		cout<<"sum(x-1,y):"<<sum(x-1,y)<<endl;
35//		cout<<"sum(x,y-1):"<<sum(x,y-1)<<endl;
36		tmp =sum(x,y)+sum(x-1,y-1)-sum(x-1,y)-sum(x,y-1);
37//		cout<<"tmp:"<<tmp<<endl;
38		if (sum(x,y)%2==0)
39		    cout<<0<<endl;
40		else cout<<1<<endl;
41	    }
42//	    cout<<"*****************"<<endl;
43//	    for ( int ii = 1 ; ii <= n ; ii++)
44//	    {
45//		for ( int jj = 1 ; jj <= n ; jj++ )
46//		{
47//		    cout<<c[ii][jj]<<" ";
48//		}
49//		cout<<endl;
50//	    }
51//	    cout<<"*************************"<<endl;
52//
53	}
54	cout<<endl;
55    }