poj 2155 Matrix

Problem

poj.org/problem?id=2155

vjudge.net/contest/146952#problem/A

Referencd

www.cnblogs.com/gj-Acit/p/3258880.html

Meaning

给一个 n * n 的矩阵 A，开始时所有值是 0。

有两种操作：

1. Q x y：询问 A[x][y] 的值是多少

2. C x1 y1 x2 y2：将以 ( x1 , y1 ) 为左下角、( x2 , y2 ) 为右上角的子矩阵中的所有值都反转

Analysis

二维线段树，记录区间翻转的次数，每次询问都将涉及的树链搜一遍，把各级修改的次数累加，是奇数次就与原来不同，偶数次就与原来相同。

因为只考虑奇偶，所以可以只用 bool 型，加法改成异或。

Code

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1000;

bool tree[2048][2048];
int n;

int query_y(int xid, int y, int l, int r, int yid)
{
	int res = tree[xid][yid];
	if(l != r)
	{
		int m = l + r >> 1;
		if(m < y)
			res ^= query_y(xid, y, m+1, r, yid<<1|1);
		else
			res ^= query_y(xid, y, l, m, yid<<1);
	}
	return res;
}

int query_x(int x, int y, int l, int r, int xid)
{
	int res = query_y(xid, y, 1, n, 1);
	if(l != r)
	{
		int m = l + r >> 1;
		if(m < x)
			res ^= query_x(x, y, m+1, r, xid<<1|1);
		else
			res ^= query_x(x, y, l, m, xid<<1);
	}
	return res;
}

void change_y(int xid, int yl, int yr, int l, int r, int yid)
{
	if(yl <= l && r <= yr)
		tree[xid][yid] ^= 1;
	else if(r < yl || yr < l)
		return;
	else
	{
		int m = l + r >> 1;
		change_y(xid, yl, yr, l, m, yid<<1);
		change_y(xid, yl, yr, m+1, r, yid<<1|1);
	}
}

void change_x(int xl, int xr, int yl, int yr, int l, int r, int xid)
{
	if(xl <= l && r <= xr)
		change_y(xid, yl, yr, 1, n, 1);
	else if(r < xl || xr < l)
		return;
	else
	{
		int m = l + r >> 1;
		change_x(xl, xr, yl, yr, l, m, xid<<1);
		change_x(xl, xr, yl, yr, m+1, r, xid<<1|1);
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int q;
		scanf("%d%d", &n, &q);
		memset(tree, false, sizeof tree);
		for(char op; q--; )
		{
			scanf(" %c", &op);
			if(op == 'Q')
			{
				int x, y;
				scanf("%d%d", &x, &y);
				printf("%d\n", query_x(x, y, 1, n, 1));
			}
			else
			{
				int xl, xr, yl, yr;
				scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
				change_x(xl, xr, yl, yr, 1, n, 1);
			}
		}
		if(t)
			putchar('\n');
	}
	return 0;
}