Rectangle Tiling

Rectangles have three types: top-row only, bottom-row only, or both rows.

Once the selected both-row rectangles are fixed, they must be non-overlapping from left to right. In every gap between two consecutive both-row rectangles, top-only and bottom-only rectangles can be scheduled independently.

For one row, define next$(x)$ as the smallest right endpoint among intervals whose left endpoint is greater than $x$. Repeatedly following next is exactly the usual earliest-finish greedy interval schedule. Make each endpoint $x$ a child of next$(x)$. When a sweep passes a right endpoint $e$, exactly the starting points in the subtree of $e$ gain one additional greedily selectable interval.

Relevant starting points are $0$ and the right endpoints of both-row rectangles. Build this tree for each row and assign DFS orders. A starting point $s$ becomes a static 2D point $(p_1(s),p_2(s))$. A subtree update in the first row is a vertical strip update on these points, while one in the second row is a horizontal strip update.

Store the static points in a 2D KD tree, maintaining each node's bounding box, maximum value, and lazy increment. Strip updates take $O(\sqrt K)$. Sweep columns from left to right. At the left endpoint of a both-row rectangle, its DP value is the current global maximum plus one. After processing one-row intervals ending at the current coordinate, activate the current coordinate as a new starting point with the best DP value of both-row rectangles ending there.

The total complexity is $O(K\sqrt K+K\log K)$. Solution written by GPT5.6