There is a better solution than the ones in the editorial (thanks to Swistakk's submission [help I can't post links]) that involves counting maximal rectangles in histograms. Here's the gist of how it works:

Basically, for each row we count the rectangles whose base touches that row. This is done by using a monotonic increasing stack on the heights. The elements of the stack are pairs of height and the lowest index such that a rectangle of that height can be made from that index to right before the current index.

From left-to-right, at the current index pop all elements larger than or equal to it. Each of these popped elements have their maximal rectangle stopped right before the current index. Let be a popped pair, the maximal rectangle has height and width where is the current index. However, we need to count for each width and height. We might try to calculate subrectangles after counting maximal rectangles by counting the 2D prefix sum (offline range addition), however we need to be careful of double counting. To do so, we only count the rectangles down to the height of the next pair in the stack or the current height if the next pair's height is lower. This is a subtraction in the 2D prefix sum.

Let be the prefix count and be the count for a rectangle of width and height . This count is not the final answer because it only counts subrectangles once even though they appear in the superrectangle multiple times. We can use simple DP by noticing that we can count rectangles of width as rectangles of width : .

On a side note, I feel like the first solution in the editorial is incomplete:

And for each and such that and , we have a subrectangle with height and width .

How are you supposed to count this efficiently?