1542. Stamps Along a Diagonal

A grid of R by C zeros is given, then q operations. Each is r1 c1 len v and means "add v to the len cells starting at (r1, c1) and stepping DOWN AND RIGHT", that is to (r1, c1), (r1+1, c1+1), ... , (r1+len-1, c1+len-1). Every segment is guaranteed to stay inside the grid.

Print the final grid.

``` R = 3, C = 4, operations (1 1 3 5) and (2 2 2 -1)

5 0 0 0 0 4 0 0 0 0 4 0 ```

``` R = 3, C = 4, one operation (1 4 1 9)

0 0 0 9 0 0 0 0 0 0 0 0 ```

``` R = 1, C = 6, operations (1 1 1 4) and (1 6 1 -4)

4 0 0 0 0 -4 on a single row no segment can be longer than one cell ```

## What most people try first

Walking the segment and adding v to each cell. A segment can be as long as min(R, C), so 2 * 10^5 operations on a 1000 by 1000 grid is 2 * 10^8 writes, and every one of them is a scattered memory access down a diagonal.

The second reflex is the four-corner rectangle stamp of problem 736. It does not apply: a diagonal segment is not a rectangle, and stamping its bounding box adds v to len * len cells instead of len.

## A difference array is about a DIRECTION, not about the axes

In one dimension, a range add is two marks and the recovery is a running total along the line. In two dimensions with rectangles, it is four marks and a running total in two directions. A diagonal segment is a one-dimensional range on a diagonal LINE, so it is two marks and a running total along that line:

``` d[r1][c1] += v d[r1+len][c1+len] -= v one step past the end, down and right

then, in reading order: d[i][j] += d[i-1][j-1] ```

## Why the recovery pass works

d[i][j] after the pass is the sum of the marks at (i-k, j-k) for every k >= 0 that stays inside the grid, which is the sum of the marks at or before (i, j) on its own diagonal. A segment contributes +v from its start and -v from one past its end, so a cell on that diagonal collects v exactly when it is at or after the start and strictly before the closing mark. That is exactly the segment.

Cells on different diagonals never interact, because the pass only ever reads up and to the LEFT along the same diagonal.

## The closing mark that falls off the grid

(r1+len, c1+len) is outside the grid whenever the segment ends on the last row or the last column, which is most of the interesting cases. Allocate (R+2) by (C+2) so the write is legal and the row and column are never printed. The one-cell segment in the top-right corner is the smallest case: its closing mark is at (2, 5) on a 3 by 4 grid, outside on the column side only.

## Why only two marks and not four

The four-mark version exists because a rectangle has two independent extents and closing it needs both, with the fourth mark repairing the overlap. A segment has ONE extent, along its own line, so the one-dimensional argument applies unchanged. Noticing that the number of marks is a property of the region's dimension, not of the grid's, is the transferable part.

## Overflow

Up to 2 * 10^5 segments of magnitude 10^9 can cross the same cell, so a value reaches 2 * 10^14. That is far past the 2147483647 a signed 32 bit integer holds, so the difference grid is 64 bit. Three such stamps already reach 3 * 10^9, which is also past it.

## Cost

O(q + R C) time and O(R C) memory.

Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `0 ≤ q ≤ 200000` - `1 ≤ r1 ≤ R` and `1 ≤ c1 ≤ C` - `1 ≤ len` and the segment stays inside the grid, so `r1 + len - 1 ≤ R` and `c1 + len - 1 ≤ C` - `-10^9 ≤ v ≤ 10^9` - when `q` is 0 no operation line follows at all - `R` and `C` are independent; the grid need not be square