The task is to find the number of rectangles with all of its squares equal. Let us try to first solve the simpler version of the task; there are only two types of squares: ~0~ and ~1~ and we need to count the number of rectangles that don't have a zero, in other words, consist of only ~1~'s.

Let us try to count these rectangles in a way that we fixate their lower right corner. Furthermore, let us try to count from left to right, going down through rows. Additionally, let us define ~a[x][y]~ as the number of ~1~'s until the first zero to the top of the matrix. (~x~ is the vertical component, ~y~ horizontal)

Let us assume that we are calculating the solution for the lower right corner ~(x, y)~. Let ~(x, z)~ be a pair so that it holds ~a[x][z] < a[x][y]~, that ~z < y~ and that ~z~ is maximal out of all possible ~z~'s. In other words, we want to know the first position to the left of our current position ~y~ so that the height of that column is smaller than the height of the column at our current position.

To continue, we need to notice that every rectangle with its right corner at the current position (current ~y~), and left corner at position ~z~ or to the left of it is actually a rectangle that has the right corner at position ~z~, extended to column ~y~. Therefore, the number of rectangles that end at ~y~ and go over ~z~ is equal to the number of rectangles ending at ~z~.

We still have to count the number of rectangles that have the left corner to the right of ~z~. The number of such rectangles is ~(y-z) \times a[x][y]~ because all columns up to ~z~ are higher than or equal to the column at ~a[x][y]~, which means that every rectangle height is possible, its width being from anything to ~y-z~.

It is necessary to somehow maintain a structure that will give an answer to the question: first column on the left, smaller than the current column. This can be done using a stack or some of the more advanced data structures such as logarithmic or tournament tree.

Using the stack, we can do this in the following way (pseudocode):

while column on stack peak is larger than current column
    pop that column from stack
y <- column left on stack peak
push current column to stack

The complexity of this algorithm on a stack is linear. After we have solved this simpler version of the task, we still need to expand the solution for the original version of the task. The expansion is fairly simple and is left for the reader to practise.