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

Indeed, after removing $$$a_0$$$, the prefix maximum remains equal to $$$a_i$$$ until we reach the first element greater than $$$a_i$$$. Therefore, for every element $$$a_i \lt a_0$$$ on this chain, its next greater element $$$a_{right_i}$$$ becomes the position where the prefix maximum increases, so its new contribution is $$$a_{right_i} - a_i$$$.

Once we reach an element $$$a_i \gt a_0$$$, all further values of $$$b$$$ remain unchanged, since $$$a_0$$$ was not the maximum anymore.

Thus, we can update the representation for the new left border by following the chain of nearest greater elements.

7. Processing the Queries

We can now process all queries offline by sorting them by their left border $$$y_1$$$.

Initially, we set $$$y_1=0$$$.

and construct the corresponding array $$$b$$$. Then we process the queries in increasing order of $$$y_1$$$. Whenever we move the current left border from $$$y_1$$$ to $$$y_1+1$$$, we apply the updates described in the previous section to every row.

After the current left border becomes equal to the left border of the query, the answer can be obtained as

Therefore, we need a data structure that supports point updates of $$$b_{i,j}$$$ and rectangle sum queries.

We can use a two-dimensional Fenwick tree for this purpose. Every change of one value of $$$b$$$ is performed as a point update, while the answer to a query is obtained using four prefix sums.

Thus, after sorting the queries by $$$y_1$$$, we maintain the correct representation of the prefix maximums for the current left border and answer every query independently.

8. Complexity of Updating b

The only remaining question is how many changes we perform when moving the left border.

Consider one row. When the left border is moved from $$$y_1$$$ to $$$y_1+1$$$, we follow the chain of nearest greater elements

while

So we need to take the contribution of these chains into account when analyzing the complexity. Let's prove that the intersection of every pair of chains is empty. This will give us a total complexity of $$$O(m)$$$.

Let $$$i$$$ and $$$j$$$ be the starting points of two chains, and assume that $$$i \lt j$$$. Suppose, for contradiction, that $$$k$$$ is a common element of the two chains.

Since $$$k$$$ belongs to the chain starting at $$$i$$$, we have $$$a_i \lt a_k$$$.

On the other hand, since $$$k$$$ belongs to the chain starting at $$$j$$$, it means that $$$a_{j-1} \gt a_k$$$.

But since $$$i \lt j$$$, the element $$$a_k$$$ is a maximum of the segment $$$[i,k]$$$, which contains $$$a_{j-1}$$$. Therefore, $$$a_k \ge a_{j-1}$$$ which contradicts $$$a_{j-1} \gt a_k$$$.

Since all elements of the chains are indices in the range $$$[0,m-1]$$$, and the chains are pairwise disjoint, the total number of updated indices in $$$b$$$ is $$$O(m)$$$.

9. Complexity

Let's analyze the complexity.

For every row, moving the left border requires following a chain of nearest greater elements. Each element can be processed only when it is reached by this procedure, so the total number of such updates over the whole process is linear in the number of elements of the row.

As shown in Section 8, the total number of updates $$$b$$$ is

Using a two-dimensional Fenwick tree, each point update and each prefix-sum query takes

Hence, maintaining $$$b$$$ takes

Each rectangle query requires four prefix sums, so all $$$q$$$ queries take

The total complexity is therefore

The memory complexity is

10 Usage.

This problem