POJ 2155: Matrix and 2D BITs

POJ 2155: Matrix

Problem Statement

Matrix

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 29825		Accepted: 10900

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

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

Source

POJ Monthly,Lou Tiancheng

Problem Statement (Simplified)

There is a N*N matrix A. Originally, each value is 0. A command "C x1 y1 x2 y2" toggles (i.e. Boolean NOT) each value in the rectangle with opposite corners (x1, y1) and (x2, y2). Another command, "Q x y", queries the value at A[x,y]. You are to write a program to parse these commands, given N and the number of commands.

The Algorithm

This looks a heck lot alike the standard BIT problem. However, it's 2D... I wonder how we would do that... with a 2D BIT! The original BIT "update" code looks like this:

void update(int x)
{
for (int i = x; i <= N; i += lb(i))
BIT[i]++;
}

However, this time, since we are applying a 2D BIT, the update code now has 2 loops:

void update(int x, int y)
{
for (int i = x; i <= N; i += lb(i))
for (int j = y; j <= N; j += lb(j))
BIT[i]++;

}

This is the base of the 2D BIT update function.

However, the update function prunes out the entire area lower than and left to (x, y). How do we fix that? Well, we simply prune the part we don't want with -1, as expressed in this diagram.

We prune the right of the "What we Want to Mark 1" with -1, and we prune the under of it with -1. But, we overpruned what is right AND what is under of "What we Want to Mark 1", making that area a total of -2. We prune that area with 1, to create the "What we Want to Mark -1" region. This picture shows all 4 steps, using a rectangle with corners (1,1) and (5,5):

Here, they prune it with 1 for all of them instead of some -1 and some 1, for at the end all we check is if the result of getsum() is odd or even.

The general idea for pruning only a desired range in 2D BITs are like this:

Step 1. Prune the BIT starting with the origin corner (left-hand upper corner) with 1.

Step 2. Prune the right-hand side of the desired area with 1, by using the right-hand upper corner. Remember 2 mod 2 = 0.

Step 3. Prune the area beneath the desired area with 1 by using the left-hand lower corner.

Step 4. Lastly, we prune the final overpruned area with 1 by using the right-hand lower corner.

And there we have, only the desired area.