Let us first count, for each cell, how many black rectangles contain that cell as their lower right corner.

Select a row ~R~. We shall define the height of a column as the number of consecutive black cells in that column, counting up starting from row ~R~. These column heights form a histogram. We traverse the row ~R~ from the first to the last column, while keeping track of "rising stairs" of black columns from the first to the current column. The number of cells contained in the "stairs" minus one equals the number of black rectangles that contain the current cell as their lower right corner. Minus one comes from the fact that we don't recognize a ~1 \times 1~ rectangle (a single cell) as a black rectangle.

We can use a similar approach to count black rectangles that contain each cell as their lower left, upper right, or upper left corner. Using this data it is easy to calculate the number of rectangles contained in each quadrant of the table for each cell as the origin.

For any two non-overlapping black rectangles, we can draw a vertical line, horizontal line, or both a vertical and horizontal line between them.

The number of rectangle pairs separated by a vertical line (case ~A~) can be calculated by selecting a column to contain the right edge of the left rectangle. Then the other rectangle will be to the right. Those two values can be calculated from previously computed values.

We can use an analogous strategy to find the number of pairs separated by a horizontal line (case ~B~).

It is also possible to calculate the number of rectangle pairs separated by both a vertical and horizontal line (case ~C~). For example, if we select a cell as the lower right corner of a rectangle, its pair will be in the lower right quadrant from that cell. The final solution is ~A+B-C~, because case ~C~ is counted twice in cases ~A~ and ~B~. The whole computation can be carried out with complexity ~\mathcal O(N^2)~.