A garden is a grid with rows rows and cols columns of beds. Each entry of sprays is a list
[r1, c1, r2, c2]: one run of a sprinkler that waters every bed (r, c) with r between r1
and r2 and c between c1 and c2, both ends included. The two corners may come in either
order (r1 may be larger than r2, and likewise for columns), and a spray may reach past the
edge of the garden, where it waters nothing. Return the number of beds inside the garden that are
watered at least k times.
Examples
Input: rows = 3, cols = 4, sprays = [[0, 0, 1, 1], [1, 1, 2, 3], [1, 0, 1, 3]], k = 2
Output: 4
Explanation: the watering counts are
1 1 0 0
2 3 2 2
0 1 1 1
and four beds reach 2.
Input: rows = 2, cols = 2, sprays = [[1, 1, -5, -5], [5, 5, 9, 9]], k = 1
Output: 4
Explanation: the first spray covers the whole garden; the second misses it entirely.
Constraints
1 <= rows, cols <= 300,1 <= k <= 10**50 <= len(sprays) <= 10**4-10**9 <= r1, c1, r2, c2 <= 10**9- The largest tests use thousands of garden-sized sprays; painting each spray bed by bed is far too slow.
Goals
- Record a rectangle update with four corner marks
- Rebuild the counts with a row pass and a column pass
- Clip rectangles that reach past the grid edge