Hey there! Let's break down your problem and questions clearly:

1. Is your solution correct? #

Absolutely! Your core logic is spot-on. Here's why:
Every query splits the current rectangle along either the x or y axis, and the largest possible rectangle after each split will always be the product of the maximum gap between consecutive x-split lines and the maximum gap between consecutive y-split lines.

Let's verify with your example:

• Initial state: x splits are [0,6], maxX=6; y splits are [0,6], maxY=6. Area = 6*6=36.
• After x=2: x splits become [0,2,6], maxX=6-2=4. maxY remains 6. Area=4*6=24 (matches your example).
• After y=1: y splits become [0,1,6], maxY=6-1=5. maxX is still 4. Area=4*5=20 (also matches).

This logic holds because any larger rectangle would require spanning across a split line, which isn't allowed—so the biggest valid rectangle must fit entirely within one of the x-axis segments and one of the y-axis segments.

2. How to optimize your solution? #

Your initial approach of traversing the entire list each time to find maxX/maxY works, but it's inefficient for large q (e.g., 10^5 queries) since each query would take O(k) time (k is the number of split lines so far). Instead, we can use specialized data structures to reduce each query's time complexity to O(log k):

Key Idea #

We can handle the x-axis and y-axis independently. For each axis, we need two things:

• A way to maintain split lines in sorted order, so we can quickly find the neighbors of a new split line.
• A way to track the maximum gap between consecutive split lines, without rechecking all gaps every time.

Recommended Data Structures & Steps #

Let's use the x-axis as an example (y-axis works exactly the same):

a. Maintain Sorted Split Lines

Use an ordered list (in Python, we can use the bisect module to keep a list sorted). When inserting a new split x=r:

1. Use bisect.bisect_left to find the index where r should be inserted.
2. Get the left neighbor (left = splits_x[index-1]) and right neighbor (right = splits_x[index]).

b. Track & Update Gaps Efficiently

To avoid rechecking all gaps, we can use a sorted multiset (like Python's SortedList from the sortedcontainers library) to store all current gaps. Here's the process:

1. Initialize:
   • splits_x = SortedList([0, n])
   • gaps_x = SortedList([n - 0])
   • maxX = n
2. When inserting x=r:
   • Find left and right as above.
   • Calculate the old gap: old_gap = right - left
   • Remove one instance of old_gap from gaps_x (since this gap is now split into two)
   • Add the two new gaps: r - left and right - r to gaps_x
   • Update maxX to gaps_x[-1] (the last element of the sorted list is the largest gap)

Alternative: Max Heap with Gap Counting

If you don't have access to SortedList, you can use a max heap plus a hash map to track valid gaps:

1. Initialize:
   • splits_x (sorted list via bisect) = [0, n]
   • heap_x (max heap, stored as negative values since Python's heapq is a min-heap) = [-n]
   • gap_count (hash map) = {n: 1}
   • maxX = n
2. When inserting x=r:
   • Find left and right, calculate old_gap = right - left
   • Decrement gap_count[old_gap] by 1 (remove it from the map if count reaches 0)
   • Add the two new gaps to gap_count (increment their counts) and push their negative values to heap_x
   • Now, clean up the heap: while the top of the heap (negative gap) corresponds to a gap not in gap_count or with a count of 0, pop it from the heap.
   • maxX = -heap_x[0]

Time Complexity #

With either approach, each query takes O(log k) time (k is the number of split lines on the axis), which is efficient enough for large q.

内容的提问来源于stack exchange，提问作者User_Targaryen