poj 2155 Matrix (트 리 배열 의 응용)

http://poj.org/problem?id=2155
n * n (n < = 1000) 의 01 행렬 에 대해 서 는 처음에는 모두 0 이 고 두 가지 조작 이 있 습 니 다.
C x1 y1 x2 y2 는 행렬 의 왼쪽 상단 과 오른쪽 하단 을 대표 하여 이 행렬 의 01 을 교환 하고 원래 0 이 었 던 것 을 1 로 바 꾸 며 원래 1 이 었 던 것 을 0 으로 바 꿉 니 다.
Q x y A [x, y] 지금 몇 이에 요?
01 의 교환 만 있 고 원래 0 이기 때문에 [x, y] 곳 이 몇 번 바 뀌 었 는 지 계산 하면 현재 이 칸 이 몇 칸 인지 확인 할 수 있 습 니 다.중요 한 것 은 [x, y] 칸 을 어떻게 빨리 계산 하 느 냐 하 는 것 이다.조작 방법 은 [x1, y1] [x1, y2 + 1] [x2 + 1, y1] [x2 + 1, y2 + 1] 칸 을 1 로 늘 리 는 것 이다. [x, y] 에 대해 서 는 [1, 1] 에서 [x, y] 의 합 이 바로 [x, y] 에서 몇 번 바 뀌 었 다.
1 차원 으로 바 뀌 면 다 교 문제 랑 비슷 한 것 같 아 요. hdu 4970.
상세 하 게 해석 하 다 

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
//#define LL long long
#define eps 1e-9
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 10000007;

int c[1010][1010];
int n,m;

int Lowbit(int x)
{
	return x&(-x);
}

void update(int x,int y, int add)
{
	while(x <= n)
	{
		int tmp = y;
		while(tmp <= n)
		{
			c[x][tmp] += add;
			tmp += Lowbit(tmp);
		}
		x += Lowbit(x);
	}
}

int sum(int x, int y)
{
	int s = 0;
	while(x >= 1)
	{
		int tmp = y;
		while(tmp >= 1)
		{
			s += c[x][tmp];
			tmp -= Lowbit(tmp);
		}
		x -= Lowbit(x);
	}
	return s;
}

int main()
{
	int test;
	int x1,y1,x2,y2;
	scanf("%d",&test);
	while(test--)
	{
		char ch[2];
		memset(c,0,sizeof(c));
		scanf("%d %d",&n,&m);
		while(m--)
		{
			scanf("%s",ch);
			if(ch[0] == 'C')
			{
				scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
				update(x1,y1,1);
				update(x1,y2+1,1);
				update(x2+1,y1,1);
				update(x2+1,y2+1,1);
			}
			else
			{
				scanf("%d %d",&x1,&y1);
				int s = sum(x1,y1);
				if(s&1)
					printf("1
");
				else
					printf("0
");
			}
		}
		printf("
");
	}
	return 0;
}