I couldn't find this particular approach in existing editorials, so I decided to share it.

1. Problem

You are given a 2D table $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns. You need to answer $$$q$$$ queries offline. Each query is four integers $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ describing a rectangle. For each query, you need to output

2. How to Approach the Solution

If we calculate the maximum for each row separately for every query, we get $$$O(qmn)$$$. We can build a Sparse Table for each row and find each maximum in $$$O(1)$$$. This reduces the total complexity to $$$O(mn\log(m) + qn)$$$. However, we can do better.

3. Removing Maximums from the Query

Let's create new table $$$b$$$ with $$$n$$$ rows and $$$m$$$ columns.

Now, if a query has $$$y_1 = 0$$$, its answer is simply

Indeed, because

4. Moving the Left Border

The main problem now is updating $$$b_{i, j}$$$ when we move the left border from $$$y_1$$$ to $$$y_1+1$$$. Let's consider one row separately and assume $$$y_1 = 0$$$, as the other cases are similar. Now, let $$$a$$$ be a one-dimensional array.

The key observation is that b and c differ only in a small number of positions. Let's define a one-dimensional array $$$right$$$, where $$$right_i$$$ is the index of the nearest element to the right that is greater than $$$a_i$$$. We can calculate the $$$right$$$ array using a monotonic stack. Let's consider two cases: $$$x_1 \ge x_0$$$ and $$$x_1 \lt x_0$$$ The first case is easy. If $$$x_1 \ge x_0$$$, we only need to change two values in $$$b$$$:

The second case is harder. If $$$x_1 \lt x_0$$$

while