PROBLEM LINK:
Author: Soumik Sarkar
Tester: Subham Das
Editorialist: Soumik Sarkar
DIFFICULTY:
MEDIUM
PREREQUISITES:
None
PROBLEM:
Given a rectangular grid of size N \times M, handle U updates that paint a subrectangle one out of 4 distinct colors. Calculate how many cells of each color exist at the end.
EXPLANATION:
We can use the fact that the final color of a cell is determined by the last update that affected it. Therefore, if the queries are processed in reverse order then the first update that affects a cell determines its color and the cell need not be considered for further updates.
Let’s call a cell active if no update has been applied to it yet. And for each cell (x, y), let R_{x,y} be the y value of the nearest active cell to its right. Similarly we can also have D_{x,y} as the x value of the nearest active cell below (x, y). Initially, all R_{x,y} = y+1 and all D_{x,y} = x+1.
When we get an update (x_1, y_1, x_2, y_2), let’s update each row in [x_1.. x_2] sequentially with something like this
update_row(x, y1, y2, color):
if y1 > y2:
return y1
if (x, y1) is active:
color_count[color] += 1
set (x, y1) to inactive
r = update_row(x, R[x][y1], y2, color)
R[x][y1] = r
return R[x][y1]
Any cell that is turned inactive once will be skipped over in all future updates, unless it is the starting point. So complexity should be \mathcal{O}(NM) plus the number of update calls.
But wait… since we are updating each row sequentially, there may be U \times N calls to update_row, which will cause TLE.
Notice that N \times M \le 4 \cdot 10^6. So we choose to perform the updates along the smaller dimension of the update after implementing a similar update_column operation. This way the number of calls to update_row or update_coloumn can be at most U \times \sqrt{4 \cdot 10^6} = U \times 2 \cdot 10^3, which fits nicely within the time limit.
AUTHOR’S SOLUTION:
Author’s solution can be found here.