1546. How Many Lie Between Two Bounds

An R by C grid is given in which every ROW is non-decreasing left to right AND every COLUMN is non-decreasing top to bottom. Then q queries arrive, each a pair lo hi.

For each query print how many cells hold a value v with lo <= v <= hi. Note that lo may be greater than hi, in which case no value qualifies and the answer is 0.

1 3 5 7 (3, 6) -> 6 2 4 6 8 (1, 9) -> 12 3 5 7 9 (10, 20) -> 0

For the first query the qualifying cells are 3 and 5 on row 1, 4 and 6 on row 2, and 3 and 5 on row 3. The second query covers the whole grid, and the third covers nothing.

5 5 5 (5, 5) -> 9 (4, 5) -> 9 (5, 6) -> 9 5 5 5 5 5 5

## What most people try first

Scanning the grid per query: O(q R C), which at q = 2 * 10^5 over a 1000 by 1000 grid is 2 * 10^11 reads. Sorting all R * C values once and binary searching each query is O(R C log(R C) + q log(R C)) and is a perfectly good answer that throws the grid's structure away.

## Count by walking the staircase

Define countAtMost(y) as the number of cells holding at most y. Stand at the BOTTOM-LEFT cell:

i = R - 1; j = 0; n = 0 while i >= 0 and j < C: if grid[i][j] <= y: n = n + (i + 1); j = j + 1 else: i = i - 1

and countBelow(y) is the same walk with a strict comparison. Then

answer = countAtMost(hi) - countBelow(lo)

clamped at 0.

## Why adding i + 1 at a time is right

When grid[i][j] <= y, the column j is non-decreasing downwards, so every cell in rows 0 .. i of that column is at most grid[i][j], hence at most y. There are i + 1 of them, and rows below i in that column were already excluded by earlier steps. So the whole column contributes exactly i + 1 and the walk moves right.

When grid[i][j] > y, row i is non-decreasing rightwards, so every cell from column j onwards in that row exceeds y. Nothing in row i can still count beyond what earlier columns already contributed, so the row is dropped.

Each step moves one index and never moves back, so a count costs O(R + C).

## Why the subtraction needs clamping

When lo > hi the set {v <= hi} is contained in {v < lo}, so the difference is NEGATIVE. The query (7, 3) on the first example gives countAtMost(3) - countBelow(7), which is 4 - 8 = -4. The answer is 0, and the clamp is the fix. That case is declared deliberately.

## Why two walks rather than one with lo - 1

Using countAtMost(lo - 1) works on integers and quietly assumes the values are integers and that lo - 1 cannot underflow. With lo = -10^9 the subtraction is still fine in 32 bits, since -1000000001 is well inside the -2147483648 floor, but writing the strict version costs one character and makes the assumption unnecessary.

## The relationship with the neighbouring problems

Problem 818 asks only whether a value occurs, and stops at the first match. Problem 780 asks for the kth smallest and uses exactly countAtMost as the predicate inside a binary search on the VALUE. This problem asks for the count directly, twice, and subtracts. The primitive is the same; what is built on top of it is not.

## Overflow

The count is at most R * C, which is 10^6, comfortably inside a signed 32 bit integer whose limit is 2147483647. The values reach 10^9, which also fits.

## Cost

O(q (R + C)) after reading the grid, and O(1) extra memory per query.

Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ lo ≤ 10^9` and `-10^9 ≤ hi ≤ 10^9` - `lo` may be greater than `hi`, and the answer is then 0 - `-10^9 ≤ each value ≤ 10^9` - every row is non-decreasing left to right and every column is non-decreasing top to bottom - `R` and `C` are independent; the grid need not be square