For solution 2, when a heavy row arrives, it uses O(N) time to count as it goes over all the 1's in all rows(i.e, count the rectangles between this heavy row with all the other rows). Consider a light row arrives, it uses O(N) time to enumerate all pairs of 1's in its row. Let the number of heavy row be h, then the time for heavy row with all the other rows is O(hN); for light row, it is O(N(R - h)), where R is the number of rows. Therefore the total counting time is O(NR). Plus the preprocessing step, it should be O(RN + RC), where C is the number of columns.

All right, here comes the **more sophisticated analysis for the light row part**. Indeed, suppose we have k light rows, each have s_1, s_2, ..., s_k 1's in their rows. Then the exact computation time for the light row part counting is the sum of (s_i)^2 over all these rows. Assume s_1 >= s_2 >= ... >= s_k, if s_1 is smaller than \sqrt(N), one can reduce s_k by 1 and add it to s_1 to get a larger sum of (s_i)^2. Therefore one could conclude that the largest value of this sum of squares happens when s_1 = s_2 = ... s_{p-1} = \sqrt(N) and s_p < \sqrt(N) for some p is roughly \sqrt(N). This gives the upper bound for the light row part which is O(N\sqrt(N)). As there are at most \sqrt(N) heavy rows and each row spends O(N) time. Therefore the time complexity is **O(N\sqrt(N) + RC)**.