Squares are dropped one at a time onto the x-axis. Square i is given as (left, side): its bottom edge spans left to left + side, and it falls straight down until it lands on the ground or on top of an earlier square. It lands on an earlier square only if their horizontal spans overlap with positive length; squares that merely touch at an edge slide past each other. Once landed, a square never moves.
Write falling_squares(positions) -> list[int] where out[i] is the height of the tallest stack anywhere after the first i + 1 squares have landed.
falling_squares([(1, 2), (2, 3), (6, 1)]) # [2, 5, 5]
# square 1 covers [1, 3) up to height 2
# square 2 covers [2, 5), overlaps it, lands at 2 and reaches 5
# square 3 covers [6, 7), lands on the ground at height 1; the max stays 5
falling_squares([(1, 2), (3, 2)]) # [2, 2] (they only touch at x = 3)
Constraints: 0 <= left <= 10**8, 1 <= side <= 10**6, up to 2 * 10^4 squares. Heights can exceed 32 bits. Comparing each square with every earlier one is O(n²); aim for O(n log n).
Show hint
Only the squares' edge coordinates matter, so map them to a small range of indices. Each drop is then "read the maximum height over a range of positions" followed by "raise that whole range to a new height", and a range structure can do both in O(log n).