首页 > 其他 > 详细

POJ 2155 Matrix 二维树状数组

时间:2014-06-05 01:54:32      阅读:352      评论:0      收藏:0      [点我收藏+]

题目来源:POJ 2155 Matrix

题意:开始矩阵都是0 2种操作 把某个子矩阵翻转 0变1 1变0 查询x y 是0还是1

思路:树状数组 记录翻转次数就行 奇数次是1 偶数次是0 

这题是区间更新 点查询   向上求和 向下更新 而且是二维的


#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1300;
int a[maxn][maxn];
int b[maxn][maxn];
int n, m;

int lowbit(int x)
{
	return x & -x;
}
int sum(int x, int y)
{
	int ret = 0;
	while(x <= n)
	{
		int Y = y;
		while(Y <= n)
		{
			ret += a[x][Y];
			Y += lowbit(Y);
		}
		x += lowbit(x);
	}
	return ret;
}

void update(int x, int y, int z)
{
	while(x > 0)
	{
		int Y = y;
		while(Y > 0)
		{
			a[x][Y] += z;
			Y -= lowbit(Y);
		}
		x -= lowbit(x);
	}
}

int main()
{
	int cas = 0; 
	int T;
	scanf("%d", &T); 
	while(T--)
	{
		scanf("%d %d", &n, &m); 
		memset(a, 0, sizeof(a));
		while(m--)
		{
			char s[10]; 
			scanf("%s", s);
			if(s[0] == 'C')
			{
				int x1, y1, x2, y2;
				scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
				update(x2, y2, 1);
				update(x1-1, y2, -1);
				update(x2, y1-1, -1);
				update(x1-1, y1-1, 1);
			}
			else
			{
				int x, y;
				scanf("%d %d", &x, &y);
				printf("%d\n", sum(x, y)%2);
			}
		}
		if(T)
			printf("\n");
	}
	return 0;
}



POJ 2155 Matrix 二维树状数组,布布扣,bubuko.com

POJ 2155 Matrix 二维树状数组

原文:http://blog.csdn.net/u011686226/article/details/27100617

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!