树状数组-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.
- 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).
- 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’）。要维护矩阵的信息，系统会要求您编写程序以接收和执行两种指令。
- C x1 y1 x2 y2（1 <= x1 <= x2 <= n，1 <= y1 <= y2 <= n）通过使用左上角为（x1，y1）和更低的矩形来改变矩阵 - 右角是（x2，y2）。
- 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个岗位