poj 2155 Matrix(二维树状数组，好题)中等难度题目，更新区域，查询单点

本文主要是介绍poj 2155 Matrix(二维树状数组，好题)中等难度题目，更新区域，查询单点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、http://poj.org/problem?id=2155

2、题目大意：

有一个n*n的矩阵，初始值时0，现在对该矩阵做两种操作，C x1 y1 x2 y2，是将这一区域的值是0的换成1,是1的换成0,Q x y查询(x,y)值是多少？

这道题目一看很简单，抬手就写了个for循环，相当于5000*1000*1000的循环，果断超时了，这样的题目就要想到用树状数组来做了，但是这道题目跟以前的树状数组还是不同的，这个是更新一个区域的值，查询一个点的值，想都想不出来哪里可以用树状数组来做，下面看网上大神的思路，很奇妙的。。。

经典的二维树状数组

这道题跟一般的树状数组操作有点不同，它是修改一片区域的值，求的是其中的一个点，我们可以这样来想！！

当我们修改一片区域的时候，我们可以分段去修改，也就是想当于树状数组中的 getsum(x,y)

当我们求其中的一个点的时候，我们可以变为统计这个点的翻转次数，凡是跟这个点相关的区间都要统计一下，

比如说在一维的情况中，

我们要使区间(a, b)内的点 + c，只需要使区间(1, b)内的点+c，而区间(1, a-1)内的点-c即可。

如果是二维的，修改矩阵(x1, y1)到(x2, y2)，即(x2, y2)+c, (x1-1,y2)-c, (x2, y1-1)-c, (x1-1,y1-1)+c。

即我们可以用getsum(x, c)修改(1, x)这个区间内的点的值，而用update(x)来求该点的值

在这里c[]数组记录了翻转次数,只不过题目要求的是01变换,所以c[]只要记录0，1就行了，奇数为1，偶数为0

3、题目：

Matrix

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 16547		Accepted: 6227

Description

Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).

We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.

1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].

Input

The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.

The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.

Output

For each querying output one line, which has an integer representing A[x, y].

There is a blank line between every two continuous test cases.

Sample Input

Sample Output

Source

POJ Monthly,Lou Tiancheng

4、二维树状数组AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1005
int c[N][N];
int n;
int lowbit(int i)
{return i&(-i);
}
void getsum(int x,int y)
{for(int i=x;i>0;i-=lowbit(i)){for(int j=y;j>0;j-=lowbit(j)){c[i][j]=c[i][j]^1;}}
}
int update(int x,int y)
{//sum统计替换的次数，次数是偶数表示输出应该是0,否则是1int sum=0;for(int i=x;i<=n;i+=lowbit(i)){for(int j=y;j<=n;j+=lowbit(j)){sum+=c[i][j];}}if(sum%2==0)return 0;elsereturn 1;
}
int main()
{int t,m,x1,y1,x2,y2,x,y;char ch[3];scanf("%d",&t);int flag=0;while(t--){if(flag==0){flag=1;}elseprintf("\n");scanf("%d%d",&n,&m);memset(c,0,sizeof(c));for(int i=1;i<=m;i++){scanf("%s",ch);if(ch[0]=='C'){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);getsum(x2,y2);getsum(x1-1,y2);getsum(x2,y1-1);getsum(x1-1,y1-1);}else{scanf("%d%d",&x,&y);printf("%d\n",update(x,y));}}}return 0;
}
/*
2
2 10
C 2 1 2 2
Q 2 2
C 1 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 2 2 2
Q 1 1
C 1 1 2 1
Q 2 1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
*/

5、简单实现超时的代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1005
int a[N][N];
int main()
{int t,n,m,x1,y1,x2,y2,x,y;char ch[3];scanf("%d",&t);int flag=0;while(t--){if(flag!=0){printf("\n");flag=1;}scanf("%d%d",&n,&m);memset(a,0,sizeof(a));for(int i=1;i<=m;i++){scanf("%s",ch);if(ch[0]=='C'){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for(int i=x1;i<=x2;i++){for(int j=y1;j<=y2;j++){a[i][j]=a[i][j]^1;}}}else{scanf("%d%d",&x,&y);printf("%d\n",a[x][y]);}}}return 0;
}

这篇关于poj 2155 Matrix(二维树状数组，好题)中等难度题目，更新区域，查询单点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！