POJ 2155 Matrix 题解 《挑战程序设计竞赛》

POJ 2155 Matrix

矩阵：频繁翻转一个二进制矩阵，求任一点值。

3.3活用各种数据结构

Binary Indexed Tree

好久没刷题了，感觉智商跌了一半。这道题是二维的Range Sum Query，直接用二维的BIT太慢。在一维POJ 3109 Inner Vertices的基础上，拓展到二维即可。一维用了2个BIT，二维得用4个2维的BIT。它们满足sum(y,x)=bit_xy(y,x)*yx + bit_y(y,x)*y + bit_x(y,x)*x + bit(y,x)，如果有好用的模板的话，这题就相当轻松了。

如图所示：

每个2DBIT可以高效地更改某一点的值以及求出区域和，但是无法高效地修改一个区域的值。这时在每个维度上使用2个BIT记录初始值和修正值，控制复杂度于O(X×T×logN×logN)。

#include <iostream>
using namespace std;

#define MAX_N 1000 + 1

typedef long long bit_t;

// 二维矩阵的区间和
struct BinaryIndexedTree2D
{

#define MAX_BIT MAX_N + 1
	bit_t data[MAX_BIT][MAX_BIT];
	int size;

	void init(int size)
	{
		memset(data, 0, sizeof(data));
		this->size = size;
	}

	// 求(0,0) 到(x,y)围成的矩形区域元素之和
	bit_t sum(int y, int x)
	{
		bit_t ret = 0;
		for (int ty = y; ty; ty -= ty&-ty)
		{
			for (int tx = x; tx; tx -= tx&-tx)
			{
				ret += data[ty][tx];
			}
		}
		return ret;
	}

	// 执行(x,y) += v
	void add(int y, int x, bit_t v)
	{
		for (int ty = y + 1; ty <= size; ty += ty&-ty)
		{
			for (int tx = x + 1; tx <= size; tx += tx&-tx)
			{
				data[ty][tx] += v;
			}
		}
	}
};

BinaryIndexedTree2D bit_xy, bit_x, bit_y, bit;
// sum(y,x)=bit_xy(y,x)*yx + bit_y(y,x)*y + bit_x(y,x)*x + bit(y,x)


//矩形[y1, y2) * [x1, x2)区域内每个元素增加v
void add(int y1, int y2, int x1, int x2, bit_t v)
{
	bit_xy.add(y1, x1, v);
	bit_xy.add(y1, x2, -v);
	bit_xy.add(y2, x1, -v);
	bit_xy.add(y2, x2, v);

	bit_x.add(y1, x1, -y1 * v);
	bit_x.add(y1, x2, y1 * v);
	bit_x.add(y2, x1, y2 * v);
	bit_x.add(y2, x2, -y2 * v);

	bit_y.add(y1, x1, -x1 * v);
	bit_y.add(y1, x2, x2 * v);
	bit_y.add(y2, x1, x1 * v);
	bit_y.add(y2, x2, -x2 * v);

	bit.add(y1, x1, y1 * x1 * v);
	bit.add(y1, x2, -x2 * y1 * v);
	bit.add(y2, x1, -y2 * x1 * v);
	bit.add(y2, x2, y2 * x2 * v);
}

// 区域和
bit_t sum(int y, int x)
{
	return bit_xy.sum(y, x) * y * x + bit_x.sum(y, x) * x + bit_y.sum(y, x) * y + bit.sum(y, x);
}

// 区域和，左开右闭
bit_t sum(int y1, int y2, int x1, int x2)
{
	return sum(y1, x1) + sum(y2, x2) - (sum(y1, x2) + sum(y2, x1));
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int X;
	scanf("%d", &X);
	while (X--)
	{
		int N, T;
		scanf("%d%d", &N, &T);
		bit.init(N);
		bit_x.init(N);
		bit_y.init(N);
		bit_xy.init(N);
		while (T--)
		{
			char cmd;
			scanf(" %c", &cmd);
			if (cmd == 'C')
			{
				int x1, y1, x2, y2;
				scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
				add(y1 - 1, y2, x1 - 1, x2, 1);
			}
			else
			{
				int x, y;
				scanf("%d%d", &x, &y);
				printf("%d\n",  (sum(y - 1, y, x - 1, x) & 1));
			}
		}
		puts("");
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2155 Matrix 题解 《挑战程序设计竞赛》