For the first subtask, we can iterate through all ~\mathcal O\left((NM)^2\right)~ sub-rectangles and check if each one is ugly. We can do each check in ~\mathcal O(N+M)~ for a total time complexity of ~\mathcal O\left((NM)^2(N+M)\right)~.

Time complexity: ~\mathcal O\left((NM)^2(N+M)\right)~

For the second subtask, we can still iterate through all possible sub-rectangles, but use an ~\mathcal O(1)~ hash to check if their first and last rows and first and last columns are identical. This reduces our total complexity to ~\mathcal O\left((NM)^2\right)~.

Time complexity: ~\mathcal O\left((NM)^2\right)~

For the final subtask, we ask the question: given two rows ~r_1~ and ~r_2~, how many ugly rectangles have first row ~r_1~ and last row ~r_2~?

Let's focus on the area of the screen between ~r_1~ and ~r_2~. Notice that there are certain "chunks" of the screen where ~r_1~ and ~r_2~'s pixels are identical. For example:

Then, observe that a rectangle with first row ~r_1~ and last row ~r_2~ is ugly if and only if:

• its first and last columns are identical, and
• its first and last columns are within the same "chunk" (otherwise, the first and last rows of the rectangle would not be identical).

Hence, we want to know the total number of pairs of identical columns that are in the same chunk. We can calculate this number in ~\mathcal O(M)~ or ~\mathcal O(M \log M)~ by sweeping over the columns from left to right, adding their hashes to a set as we go along, and processing and clearing the set when we reach the end of a chunk. Repeating this for all pairs ~(r_1, r_2)~, we get a total time complexity of ~\mathcal O\left(N^2 M\right)~ (with a possible extra log factor).

Finally, notice that ~\min(N, M)~ cannot be larger than ~\sqrt{NM}~. Thus, if we choose ~N~ to be the smaller of the two, our time complexity becomes ~\mathcal O\left(NM \sqrt{NM}\right)~.

Time complexity: ~\mathcal O\left(NM \sqrt{NM}\right)~ or ~\mathcal O\left(NM \sqrt{NM} \log(NM)\right)~