PROBLEM LINK:
Author: Animesh Fatehpuria
Editorialist: Arjun P
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Math, Persistent Segment Trees
PROBLEM:
You have an N \times N grid. Given N and K, perform U updates: given x and y, mark all cells (r, c) satisfying
|r - x| + |c - y| \le K as destroyed. Now answer Q queries online. In each query, you are given x and y, and you have to say whether the cell (x, y) is destroyed or not.
QUICK EXPLANATION
Transform the grid so that updates/queries based on Manhattan distance become rectangular updates. From now on all updates/queries will be done on the transformed grid.
For each bomb, instead of marking all the cells destroyed due to that bomb, only mark the cell where that bomb has been placed. Thus, updates become point updates. Now, to find out if a cell (x, y) is destroyed, just check if any of the cells within K Manhattan distance of (x, y) contain bombs. This Manhattan query turns into a rectangular query in the transformed grid. Implementing rectangular queries with 2D implicit segment trees or implicit quadtrees proves too slow. Instead, use a 1D persistent segment tree: root[i] is a segment tree containing all the updates from row 1 to row i. Thus any rectangular query from (x_1, y_1) to (x_2, y_2) can be computed as:
root[y_2].query(x_1, x_2) - root[y_1 - 1].query(x_1, x_2)
EXPLANATION
In this discussion, when I say a cell (x_1, y_1) is within K distance of another cell (x_2, y_2), I mean the Manhattan distance, i.e. it holds true that |x_1 - x_2| + |y_1 - y_2| \le K.
In each update, given a cell (x, y), we have to mark all cells (r, c) satisfying |r - x| + |c - y| \le K as being destroyed. Observe that this is basically a diamond centered at (x, y). The diameter of the diamond is 2K + 1, if it fits on the grid. Otherwise, obviously, it will get cut off by the edges of the grid.
We do not have any data structure that can perform this sort of diamond-shaped range update efficiently. How do we get around this?
Observe that if we rotate the grid 45 degrees to the right, our diamond-shaped updates will become rectangular. Say we have a 5*5 grid with an update at (3,3) with K = 2, this is how the grid updates will look like:
The updates on the rotated grid would be of this form:
This can be implemented by mapping x and y to x' and y' in the rotated grid. You can use several mappings. The one used in the picture is as follows:
Given (x,y) -> x' = x + y - 1 and y' = y - x + N
Now our diamond-shaped update has turned into a rectangular update. But we still have no efficient way of implementing rectangular updates. How can we avoid having to perform 2D range updates?
We know that a bomb destroys all cells within K distance of it. But note that this implies that a cell is destroyed iff a bomb is within K distance of it. So then, instead of marking all the destroyed cells, what if we marked only the cells containing the bomb? i.e. we mark only the input cell (x, y). Now, to find out if a given cell is destroyed, we need to find out if any of the cells within K distance of it have been marked. This is again a diamond-shaped query, but on the transformed grid, this is a rectangular query. Thus, instead of performing rectangular updates and point queries, we can perform point updates and rectangular queries.
But how do we implement 2D range queries? Note that N \le 5\times 10^5, so a normal 2D segment tree would not work. We could do this using an implicit 2D segment tree. However, this is very annoying to implement and, moreover, it has a very high constant factor and will not even run in the time limit. Instead, let’s be a bit more clever. Note that all the updates occur before all the queries. Therefore, we can do the updates offline.
We could do this with N segment trees, where the i^{th} (0 \le i \le N) segment tree contains the cumulative sums of all the rows from 1 to i. (rows are 1-indexed.) i.e., the j^{th} element in the i^{th} segment tree contains the sum grid[1][j] + grid[2][j] + \ldots + grid[i][j]. Note that grid[i][j] is the number of bombs at the position (i, j) in the transformed grid. The 0^{th} tree will be filled with zeroes. Let’s refer to the i^{th} tree as tree[i]. We have:
tree[i][j] = grid[1][j] + grid[2][j] + \ldots + grid[i][j]
Hence, sum of grid from (x_1, y_1) to (x_2, y_2) can be found as
(tree[x_2][y_1] + tree[x_2][y_1 + 1] + \ldots + tree[x_2][y_2]) - (tree[x_1 - 1][y_1] + tree[x_1 - 1][y_1 + 1] + \ldots + tree[x_1 - 1][y_2])
Convince yourself of this fact before moving on. This is the same as
tree[x_2].query(y_1, y_2) - tree[x_1 - 1].query(y_1, y_2)
But obviously it is not possible to maintain 5 \times 10^5 different segment trees. However, we can implement this with implicit persistent segment trees. Initially for tree[0], implicitly assume all the cells to be zero. Then, to create tree[i], just add all elements on the i^{th} row to tree[i - 1]. Note that we are adding updates in ascending order of their row numbers in the transformed grid. This is an offline algorithm and is valid only because all queries occur after all updates. Since there are only U updates, there are only U elements and so this can be done in O(UlogN) time using persistent segment trees.
Now, as was explained before, to find out if the cell (x, y) is destroyed, we just need to perform a rectangular query, and that can be done in two 1D segment tree queries as per the above formula. So, all queries together take O(QlogN) time.
Final Complexity: O((U + Q)\log{}N)