hackercupai/hackercup huggingface dataset:
As in Chapter 1 of this problem, we'll process the rectangles one by one while computing \(P_{1..N}\). When processing the \(i\)th rectangle, we can't afford to compute the perimeter of the union of the first \(i\) rectangles from scratch (as this would result in an inefficient algorithm with time complexity at least \(O(N^2)\)), so we'll instead compute how the inclusion of this rectangle affects the existing rectangle union (and therefore how \(P_i\) differs from \(P_{i-1}\), assuming that \(P_0 = 0\)).

Because each rectangle is no taller than all existing ones, the exact heights of those existing ones end up not mattering — only their x-coordinates do. As such, we'll maintain an ordered set of non-intersecting intervals of x-coordinates which the rectangle union spans.

Let's separately consider the amount of horizontal and vertical perimeter added for the \(i\)th rectangle. The total horizontal perimeter of the rectangle union is always just the sum of the lengths in the intervals in our set, multiplied by two (to account for both the top and the bottom). Meanwhile, we can observe that the \(i\)th rectangle contributes \(2H_i\) vertical perimeter, minus \(2H_i\) for each existing interval that it overlaps (inclusively) with (as the perimeter is prevented from going all the way down to y-coordinate \(0\) and back up to \(H_i\).

Based on the above observations, as long as we're able to update the ordered set of intervals for each new rectangle (by iterating over ones that it overlaps with, deleting them, and then inserting a new interval spanning the affected x-coordinates), we can also easily update the union's current perimeter along the way. Efficient ordered sets are supported in many programming languages, backed by BBSTs (balanced binary search trees) and capable of supporting the necessary searching, deletion, and insertion operations in logarithmic time in the number of elements in the set. Therefore, given that our ordered set will contain at most \(N\) elements (one interval per rectangle) and that each rectangle's interval will be inserted/deleted at most once, this approach yields a time complexity of \(O(N log(N))\).