2013
11-10

# 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].

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.

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.

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


import java.util.Scanner;

public class Main {

private static int[][] matrix = new int[1001][1001];
private static int n;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int testNum = sc.nextInt();
for (int i = 0; i < testNum; ++i) {
matrix = new int[1001][1001];
n = sc.nextInt();
int t = sc.nextInt();
for (int j = 0; j < t; ++j) {
String c = sc.next();
if (c.equals("C")) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
change(x1 , y1 , 1);
change(x1 , y2+1 , -1);
change(x2+1 , y2+1 , 1);
change(x2+1 , y1 , -1);
} else if (c.equals("Q")) {
int x = sc.nextInt();
int y = sc.nextInt();
int v = getSum(x, y) & 1;
// System.out.println(getSum(x , y));
if (v == 0)
System.out.println(0);
if (v == 1)
System.out.println(1);
}
}
System.out.println();
}
}

public static void change(int x1, int y1, int x2, int y2) {

for (int i = x1; i <= x2; ++i) {
change(i, y1, 1);
change(i, y2 + 1, -1);
}
// for (int i = x1; i <= x2; ++i) {
// for (int j = y1; j <= y2; ++j) {
//
// if (matrix[i][j] == 0)
// matrix[i][j] = 1;
// else
// matrix[i][j] = 0;
// }
// }
}

public static int lowbit(int i) {
return i & -i;
}

public static void change(int i, int j, int value) {
while (i <= n) {
int temp = j;
while (temp <= n) {
matrix[i][temp] += value;
temp += lowbit(temp);
}
i += lowbit(i);
}
}

public static int getSum(int i, int j) {
int sum = 0;
while (i > 0) {
int tmp = j;
while (tmp > 0) {
sum += matrix[i][tmp];
tmp -= lowbit(tmp);
}
i -= lowbit(i);
}
return sum;
}

}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。