首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >POJ 2155 Matrix(二维树状数组)

POJ 2155 Matrix(二维树状数组)

作者头像
Ch_Zaqdt
发布2019-02-26 13:19:28
1.1K0
发布2019-02-26 13:19:28
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

题目链接:http://poj.org/problem?id=2155

       题意是给一个n*n的全是0的矩阵,然后有T次询问,有两种操作,一是让(x1,y1)到(x2,y2)的值取反(0变1,1变0),第二个是询问(x,y)的值。

       暴力大法好,但是会超时,所以这道题需要用树状数组来写,依照别的博客的例子来写,首先我们要先看一维数组的性质,对于l到r的值取反,我们的操作就是pre[l]++,pre[r+1]++,因为这道题只有0和1,所以树状数组维护的是被修改的次数,所以查询的操作就是就是前i个的和mod2,千万不要把这个当成数组理解,因为是树状数组,所以是以lowbit位进行加减操作的。

       拓展到二维就涉及了一下容斥原理,先看一下下图。

       首先我们先让(x1,y1)到(n,n)的pre[i][j]++,然后从(x2+1,y1)和(x1,y2+1)到(n,n)也都加了1,所以再让(x2+1,y1)和(x1,y2+1)到(n,n)再加1,相当于一维数组的pre[r+1]++一样,然后对于(x2+1,y2+1)到(n,n)一共加了3次,所以需要再加一次变成偶数。


AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1005
using namespace std;
int T;
int n,m;
char str[10];
int pre[maxn][maxn];

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

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

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

int main()
{
	scanf("%d",&T);
	while(T--){
		memset(pre,0,sizeof(pre));
		scanf("%d%d",&n,&m);
		while(m--){
			scanf("%s", str);
			if(str[0] == 'C'){
				int x1,y1,x2,y2;
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				Update(x1, y1);
				Update(x2 + 1, y1);
				Update(x1, y2 + 1);
				Update(x2 + 1, y2 + 1);
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				printf("%d\n",Query(x, y) % 2);
			}
		}
		if(T) puts("");
	}
	return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年01月16日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档