Count the Rectangles of Ones
Count all rectangular submatrices consisting entirely of 1s, of every size including
single cells.
1 1
1 1 -> 9 four singles, two horizontal pairs, two vertical pairs, one full
## Why problem 536's trick does not carry over
536 counts SQUARES by summing the per-cell table from 534, because the largest square ending
at a cell determines how many squares end there: sides 1 through k, nested.
Rectangles are not nested that way. The rectangles ending at a cell have many widths and many heights, and no single number per cell determines how many there are.
So the count has to be built rather than read off.
## Count by bottom-right corner, walking up
Every rectangle has exactly one bottom-right corner, so grouping by it counts each once.
For a fixed corner (r, c), first compute the run of consecutive 1s ending at (r, c)
along its row:
width[r][c] = number of consecutive 1s ending at (r, c) going left
Now walk UPWARD from row r, keeping the running minimum of width over the rows visited:
mn = width[r][c]
for rr from r down to 0:
mn = min(mn, width[rr][c])
if mn == 0: stop
total += mn
## Why the running minimum is the count
A rectangle with bottom-right corner (r, c) and height h must have every one of its h
rows extend at least as far left as its width. So the widest it can be is the MINIMUM of
width over those h rows, and every width from 1 up to that minimum gives a distinct
rectangle.
So each height contributes exactly the running minimum, and adding them as the walk goes up counts every rectangle with that corner.
Stopping when the minimum hits 0 is not just an optimisation: rows above a zero cannot contribute, and continuing would add nothing but would cost time.
## Cost
Time O(m n min(m, n)), since the upward walk is bounded by the number of rows. Space
O(m n).
The full enumeration of every corner pair is O(m^2 n^2) and is worth stating first.
There is an O(m n) method using a monotonic stack per row, in the spirit of problem 535,
and it is considerably harder to get right. Knowing it exists is enough.
## What the tests pin down
1 1 / 1 1 answers 9 and 1 1 1 / 1 1 1 / 1 1 1 answers 36. Both are small enough to
count by hand, and 36 is the number of ways to choose two horizontal boundaries from four
and two vertical boundaries from four, which is 6 * 6.
That closed form only holds for a completely filled grid, and checking it there is a good way to confirm the walk is not off by one.
1 0 1 / 0 1 0 / 1 0 1 answers 5, five isolated cells, which is the same answer as problem
536 gives on that grid because nothing larger than a single cell exists either way.
## Overflow
The count reaches roughly (m(m+1)/2)(n(n+1)/2), which at 200 by 200 is about 4 * 10^8.
That fits in 32 bits but the running total is worth keeping in 64.