hackercupai/hackercup huggingface dataset:
As in Chapters 1 and 2 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\)).

Unlike in Chapter 2, the heights of the existing rectangles do matter in this chapter. A convenient way to maintain information about them is with an ordered set of vertical line segments (or "height changes") present in the union's perimeter. Each of these is a tuple \((x, y_1, y_2)\) indicating that, at x-coordinate \(x\), the top portion of the perimeter moves up/down from y-coordinate \(y_1\) to y-coordinate \(y_2\) when tracing the perimeter from left to right.

When processing the \(i\)th rectangle, we can begin by tentatively adding on its full perimeter (\(2(W_i + H_i)\)) to the union's current perimeter, and then separately consider the amount of horizontal and vertical perimeter we've overcounted. Similarly to Chapter 2, the total horizontal perimeter of the rectangle union is equal to twice the total length of x-coordinates spanned by at least one rectangle, meaning that the amount of overcounted horizontal perimeter is twice the total length of x-coordinates spanned by at least one existing rectangle within the interval \([L_i, L_i + W_i]\). We can tally that up by iterating over the height changes which the \(i\)th rectangle overlaps with, noting that the interval from a height change \((x, y_1, y_2)\) to the next height change is spanned by an existing rectangle if and only if \(y_2 > 0\). As for overcounted vertical perimeter, each existing height change which the \(i\)th rectangle overlaps (inclusively) with is entirely swallowed up and should no longer contribute its vertical length to the union's perimeter. Furthermore, the height of the existing perimeter at x-coordinate \(L_i\) (computable by looking at the nearest height change before or after that x-coordinate) should be subtracted (as the perimeter actually only goes down from the top of the \(i\)th rectangle to that y-coordinate rather than all the way to \(0\)), and the same applies for x-coordinate \(L_i + W_i\).

Based on the above observations, as long as we're able to update the ordered set of height changes for each new rectangle (by iterating over ones that it overlaps with, deleting them, and then inserting new ones at its left and right ends if appropriate), we can also easily update the union's current perimeter along the way. As in Chapter 2, we'll use an ordered set implementation capable of supporting the necessary searching, deletion, and insertion operations in logarithmic time (using a BBST). Given that our ordered set will contain at most \(2N\) elements (two height changes per rectangle) and that each rectangle's height changes will be inserted/deleted at most once, this approach yields a time complexity of \(O(N log(N))\).