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