Try to do it like this: fix two horizontal lines and count the number of rectangles, opposite sides of which lie exactly on these lines. It will be O(n^3) but with good constant.

I believe I have a reasonable (in terms of time complexity) solution, but you have to provide the link to problem so everyone is sure that it's not from an ongoing contest.

I think I have something like $$$O(n^2 \alpha(n))$$$, where $$$\alpha(n)$$$ is the inverse Ackerman function.

First of all, for each element, find the closest element to the right of it that is different from it. It can be done in $$$O(n^2)$$$ as follows: if $$$a[i][j] \ne a[i][j + 1]$$$, then $$$j + 1$$$ is the answer for $$$a[i][j]$$$ (we will have to store the column index for that closest element); otherwise, if $$$a[i][j] = a[i][j + 1]$$$, then the answer for $$$a[i][j]$$$ is the answer for $$$a[i][j + 1]$$$. We will need that information later.

Okay. Now, let's fix the left border of our rectangle (let it be $$$l$$$), iterate on the right border (let it be $$$r$$$), and calculate the number of rectangles meeting our constraints that have left border in $$$l$$$ and right border in $$$r$$$. Let's analyze when some row $$$i$$$ can appear in the subrectangle we are interested in. If the elements from $$$l$$$-th to $$$r$$$-th in that row are not all the same, then this row is clearly bad and cannot be used — otherwise, it can be used. The trick is that, if we look at the next different element for $$$a[i][l]$$$, its column index is equal to the first value of $$$r$$$ when our row becomes bad.

When analyzing the good rows, if there are $$$k$$$ adjacent good rows having the same number in $$$a[i][l]$$$, they add $$$\frac{k(k+1)}{2}$$$ to the answer. We can maintain these "components" of good rows as follows: initialize a DSU and start iterating on $$$r$$$ from the maximum possible value to the minimum possible. For each row, we know the moment when it becomes good — and, using something like sweep line approach, we may shift $$$r$$$ to the left, and if some row becomes good, create a component for it in DSU and try to merge it with the components for adjacent rows (if they are good).