poj 2155 Matrix

Problem

poj.org/problem?id=2155

vjudge.net/contest/146952#problem/A

Meaning

一个 N * N 的矩阵 A，初始时全部值为 0，有两种操作：

1. C x1 y1 x2 y2：将以（x1，y1）为左下角、（x2，y2）为右上角的子矩阵的所有值做 0-1 翻转；

2. Q x y：询问 A[x][y] 的值

Analysis

二维线段树的成段更新，结点记录的是对应区域的总修改次数。

易知，修改奇数次的值与原来相反，偶数次则不变。所以只与修改次数的奇偶性有关（可以将 int 改用 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;
}