736. Stamping Rectangles Onto a Grid
A grid of R by C zeros is given. Then q updates arrive, each r1 c1 r2 c2 v, meaning
"add v to every cell of the rectangle from (r1, c1) to (r2, c2) inclusive". Rows and
columns are numbered from 1.
Print the final grid.
``` R = 2, C = 3, updates (1 1 2 2 1) and (2 2 2 3 5)
1 1 0 1 6 5 ```
## Four corner stamps, not two
In one dimension a range add is two writes, at l and at r + 1 (problem 721). In two
dimensions the rectangle has four corners, and each one needs a mark:
d[r1][c1] += v
d[r1][c2 + 1] -= v
d[r2 + 1][c1] -= v
d[r2 + 1][c2 + 1] += v
The first opens an infinite quadrant of +v going down and right. The next two close it off
past the right edge and past the bottom edge. The fourth ADDS BACK the region beyond both,
because the two closers between them removed it twice.
That fourth stamp is inclusion-exclusion, the same correction problem 729 needs in its query,
and here it is needed in the UPDATE. Leaving it out subtracts v from everything below and to
the right of the rectangle, which is invisible whenever the rectangle reaches either far edge.
## Recovering the grid
Run a two-dimensional prefix sum over the stamps, in place:
d[r][c] += d[r-1][c] + d[r][c-1] - d[r-1][c-1]
after which d[r][c] is the final value of that cell. Every update cost four writes whatever
its size, and the single recovery pass costs O(R C).
## The two techniques are inverse, in both dimensions
A 2D prefix sum makes rectangle QUERIES constant time. A 2D difference array makes rectangle UPDATES constant time. Problem 729 is one direction and this is the other, and the same four-term inclusion-exclusion appears in both, once in the query and once in the update.
Noticing that the correction moves from one end of the pipeline to the other is worth more than either formula.
## Sizing
The stamps write at r2 + 1 and c2 + 1, which reach R + 1 and C + 1. Allocate
(R + 2) by (C + 2) so those rows and columns exist and are simply never printed.
## Overflow
2 * 10^5 updates of 10^9 stack to 2 * 10^14 on one cell.
## What most people try first
Walking every cell of every rectangle. One update can cover the whole grid, so 2 * 10^5
updates over a 1000 by 1000 grid is 2 * 10^11 writes. Each update below costs four,
whatever its size.
## Cost
Time O(R C + q). Space O(R C).
Constraints - `1 ≤ R, C ≤ 1000` - `0 ≤ q ≤ 200000` - `1 ≤ r1 ≤ r2 ≤ R` - `1 ≤ c1 ≤ c2 ≤ C` - `-10^9 ≤ v ≤ 10^9`
Input
The first line contains three integers R, C and q.
Each of the next q lines contains five integers r1, c1, r2, c2 and v.
Output
Print R lines of C integers, the final grid, space separated.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.