树状数组-Matrix

题目链接
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

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

Sample Output

1
0
0
1
Translate
有一个N*N的矩阵,元素值只可能是0或1。现在有两种操作:

1.C x1 y1 x2 y2:将矩形(x1,y1,x2,y2)的元素全部取反。

2.Q x y:查询(x,y)处的值。

输入数据:
第一行给出测试数据的组数X,接下来有X组数据,每组数据的第一行有两个整数N和T。N表示矩阵的边长,T表示操作的次数。N<=1000,T<=50000.接下来T行操作,如上所示。

输出数据:
对于每组数据的每次查询,输出一个整数,表示查询的结果。

给定N * N矩阵A,其元素为0或1.A [i,j]表示第i行和第j列中的数字。最初我们有A [i,j] = 0(1 <= i,j <= N)。

我们可以通过以下方式更改矩阵。给定一个左上角为(x1,y1)且右下角为(x2,y2)的矩形,我们使用“not”操作更改矩形中的所有元素(是否为’0’然后更改它变为’1’否则将其变为’0’)。要维护矩阵的信息,系统会要求您编写程序以接收和执行两种指令。

  1. C x1 y1 x2 y2(1 <= x1 <= x2 <= n,1 <= y1 <= y2 <= n)通过使用左上角为(x1,y1)和更低的矩形来改变矩阵 - 右角是(x2,y2)。
  2. Q x y(1 <= x,y <= n)查询A [x,y]。
    输入
    输入的第一行是整数X(X <= 10),表示测试用例的数量。以下X块表示测试用例。

每个块的第一行包含两个数字N和T(2 <= N <= 1000,1 <= T <= 50000),表示矩阵的大小和指令的数量。以下T行各自表示具有格式“Q xy”或“C x1 y1 x2 y2”的指令,其已在上面描述。

产量
对于每个查询输出一行,其具有表示A [x,y]的整数。
每两个连续测试用例之间有一个空白行。
样本输入

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
样本输出
1
0
0
1
翻译
有一个N * N矩阵,其元素值只能是0或1.现在有两个操作:

1.C x1 y1 x2 y2:反转矩形的所有元素(x1,y1,x2,y2)。

2.Q x y:查询(x,y)处的值。

输入数据:

第一行给出测试数据组X的数量,然后是X组数据,每组数据的第一行有两个整数N和T. N表示矩阵的边长,T表示数字的运作。 N <= 1000,T <= 50000。下一个T线操作如上所示。

输出数据:

对于每组数据的每个查询,输出一个指示查询结果的整数。
https://blog.csdn.net/qq_43516113/article/details/90675805

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int MM= 5010;
int h[MM][MM];
int n, m;
int lowbit(int x)
{
	return x & (-x);
}
void updata(int x, int y, int val)
{
	int i, j;
	for (i=x; i<=n; i+=lowbit(i))
		for (j=y; j<=n; j+=lowbit(j))
			h[i][j] += val;
}
int add(int x, int y)
{
	int i, j, ans = 0;
	for (i=x; i>0; i-=lowbit(i))
		for (j=y; j>0; j-=lowbit(j))
			ans += h[i][j];
	return ans;
}
int main()
{
	int T, i, j, ans;
	int x, y, x1, y1, x2, y2;
	char c;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&n,&m);
		for (i=1; i<=n; i++)//清零
			for (j=1; j<=n; j++)
				h[i][j] = 0;
		for(i=1; i<=m; i++)
		{
			scanf("%c",&c);
			scanf("%c",&c);
			if (c== 'C')//更新
			{
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//反转矩阵
				updata(x1, y1, 1);
				updata(x1, y2+1, -1);
				updata(x2+1, y1, -1);//这里 改为为1也可以;
				updata(x2+1, y2+1, 1);
			}
			else if (c == 'Q')//查询
			{
				scanf("%d%d",&x,&y);
				ans = add(x, y);
				ans %= 2;
				printf("%d\n", ans);
			}
		}
		if (T != 0)//格式要注意;
			printf("\n");
	}
	return 0;
}
全部评论

相关推荐

10-15 03:05
门头沟学院 Java
CADILLAC_:凯文:我的邮箱是死了吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务