## Editorial for DMOPC '20 Contest 5 P4 - Slacking Off

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AvaLovelace

For the first subtask, we can iterate through all sub-rectangles and check if each one is ugly. We can do each check in for a total time complexity of .

Time complexity:

For the second subtask, we can still iterate through all possible sub-rectangles, but use an hash to check if their first and last rows and first and last columns are identical. This reduces our total complexity to .

Time complexity:

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

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

Then, observe that a rectangle with first row and last row 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 or 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 , we get a total time complexity of (with a possible extra log factor).

Finally, notice that cannot be larger than . Thus, if we choose to be the smaller of the two, our time complexity becomes .

Time complexity: or