PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
+1, -1 Trick
PROBLEM:
You have a n \times n binary grid. There are q operations, which involves flipping all the bits in a subrectangle. Output the final grid.
EXPLANATION:
For subtask 1, iterating through all bits in the subrectangle and flipping them naively gives a simple O(qn^{2}) solution.
To solve the full task, we need to make the update process faster. First, let’s consider the problem in 1D. Suppose we only have a 1 \times n grid instead. Let a_{1}, a_{2}, ..., a_{n} be the original bits. We define a new sequence d_{1}, d_{2}, ..., d_{n + 1}, so that d_{i} = a_{i} - a_{i - 1} for 2 \le i \le n, d_{n + 1} = a_{n}, d_{1} = a_{1}. Then, to flip a range [l, r], we just flip d_{l} and d_{r + 1}, and the resulting values of a_{i} can be restored with a simple loop at the end.
The 2D case is similar. First, we define the sequence d for each row, and now we note that when we update a subrectangle, we’re effectively performing range [l, r] updates of a subsegment of d_{i} in a column. We can use the same trick again to reduce each query to flipping 4 corners of a rectangle. Finally, we can restore the grid by taking the prefix sums on rows and columns. You can see the code for the details.
The complexity of the solution is O(q + n^2).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.