Subtask 1 [20%]

For this subtask, it sufficed to iterate through each valid element in the grid. The key was to find an efficient way to calculate the range maximum of any subarray of a particular row. This could be accomplished by using ~N~ independent sparse tables, one for each row. Then, for each element, you simply calculated the size of the bottom row (~1+(R-1)B~), and iterated to the top row, reducing the width of your query by ~B~ each time.

This subtask also rewarded intended solutions with a suboptimal rectangle query

Subtask 2 [80%]

The idea here was to consider the sparse table algorithm - a query of size ~2K~ could be easily calculated if you knew the answer to all of the queries of size ~K~. Hence, if we wished to find the answer for all triangles with ~8~ rows, we could find the answer to all triangles with ~4~ rows, which used triangles with ~2~ rows, which in turn used triangles with ~1~ row. If we had an odd number of rows, then we could use triangles with ~\frac{n+1}2~ rows, roughly preserving the "halving" behavior. Notice that we actually only need to consider ~O(\log N)~ distinct dimensions, allowing for an ~O(N^2\log N)~ solution.

Now the problem becomes how we can "combine" triangles. Consider this figure, which decomposes a triangle with 6 rows and ~B=2~ into a rectangle and two triangles with ~\frac 62=3~ rows:

Then, in this case, if we calculate all triangles of size ~3~, we can also efficiently calculate all triangles of size ~6~.

So, our query becomes much simpler - calculating the maximum of a "rectangle shape". We can use a max-queue to do this (a helpful link is here; alternatively, you can use two max-stacks, one for the "front" of the queue when pushing and one for the "back" when popping).

Using this data structure, for any rectangle of height ~H~ and width ~W~, we can use the max-queue to calculate the maximum in all ~1\times W~ rectangles (run it on each row as if it were an array). Then, iterate vertically, taking maximum of all ~H\times W~ rectangles (notice that we already know the maximum of each "row" of the rectangle).