My approach: Let B_k be the bounding box of all numbers from 1 to k.

If area(B_k) = k, then B_k is beautiful. Conversely, if R is a beautiful rectangle and area(R) = k, then area(B_k) = k. And finally, if area(B_k) = k, then area(B_k + 1) > k, because if R = B_k is beautiful, then either R_k + 1 or C_k + 1 is outside of the bounding box B_k. Without loss of generality let it be R_k + 1. It follows that k + 1 is the first contestant at row R_k + 1.

So, all we need to remember is the contestant with the lowest id that is in the row i, and the contestant with the lowest id that is in the column j. We can do this by simply maintaining an ordered set of the indices of contestants for each row and column. This can be maintained in per query. Using this, we obtain H + W candidates on the beautiful rectangles in O(H + W) time and we simply check all of them.

To check a candidate for a rectangle, we have a segment tree for calculating the minimum/maximum row/column on a range. This gives us time algorithm to process one query.

Combined together, this is .

Lets define a beautiful box B_k as a box containing only numbers 0 to k-1 I would sore in array arr[id] = {r, c} the position of each contestant. Then for a bounding box B_k to exist the prefix arr[0..k] should form a rectangle. For that I get the min/max for column/row in the prefix of size k and check if the rectangle is exactly of area k. If yes then that is one box. So I compute this in O(HW) and build an array stating if B_k is a bounding box or not. When each query arrives I will update positions a and b and recompute the positions of the array in the range a and b in O(|a - b|).