POJ 2155 2 Dツリー配列

題意:矩形の左上角と右下角(マトリクスに似ている)を与え、矩形に囲まれた点はその値(0,1)を変更し、ある点の値を出力するようにいくつかの操作を与える.本題は領域を変えて点を求めることです.ある点の変化回数を2 Dツリー配列で記録します.まず、c[1],c[2],c[3],c[4],c[5],....c[10]は、c[3]-c[5]間の領域を変更するには、c[3]を1回(その後の点はすべて1回)変更してからc[6]を1回変更する必要があると仮定し、これにより、c[6]とその後の点は2回変更され、すなわち不変に相当する.

#include <iostream>
using namespace std;

int c[1010][1010], n;

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

void modify ( int x, int y )
{
	for ( int i = x; i <= n; i += lowbit(i) )
	{
		for ( int j = y; j <= n; j += lowbit(j) )
			c[i][j]++;
	}
}

void update ( int x1, int y1, int x2, int y2 )
{
	modify ( x1, y1 );
	modify ( x2 + 1, y2 + 1 );
	modify ( x1, y2 + 1 );
	modify ( x2 + 1, y1 );
}

int sum ( int x, int y )
{
	int total = 0;
	for ( int i = x; i > 0; i -= lowbit(i) )
	{
		for ( int j = y; j > 0; j -= lowbit(j) )
			total += c[i][j];
	}
	return total;
}

int main()
{
	int t, q, x1, y1, x2, y2;
	char oper[5];
	scanf("%d",&t);
	while ( t-- )
	{
		scanf("%d%d",&n,&q);
		memset(c,0,sizeof(c));
		while ( q-- )
		{
			scanf("%s",oper);
			if ( oper[0] == 'C' )
			{
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				update ( x1, y1, x2, y2 );
			}
			if ( oper[0] == 'Q' )
			{
				scanf("%d%d",&x1,&y1);
				printf("%d
", sum ( x1, y1 ) % 2 );
			}
		}
		putchar('
');
	}
	return 0;
}