Subtask 1

We observe the matrix can be compressed ~n~ times if and only if ~N~ and ~M~ are multiples of ~2^n~, and the edges of the outline formed from all the rectangles are at multiples of ~2^n~ on the grid.

Therefore, we use a 2D difference array to compute the state of the binary matrix, then brute force all the row and column positions where the matrix changes value. The answer is the largest ~n~ such that ~2^n~ divides all of these positions and the dimensions of the grid.

Time complexity: ~\mathcal O(NM)~

Subtask 2

We apply the solution from the previous subtask, but with coordinate compression.

Time complexity: ~\mathcal O(\min(NM, K^2 + K \log(N+M)))~

Subtask 3

We can efficiently compute the edge positions by doing line sweep across the rectangles with a lazy segment tree supporting range increment and range minimum query operations. We sweep each dimension independently, using the segment tree to maintain the number of overlapping rectangles in the other dimension. Any rectangle edge causing the number of overlapping rectangles at a point to change from ~0~ to ~1~ or ~1~ to ~0~ is an edge we need to consider. We can check this with an RMQ before each event.

Time complexity: ~\mathcal O(K \log K + K \log(N+M))~

Subtask 4

We apply the solution from the previous subtask, but with coordinate compression.

Time complexity: ~\mathcal O(K \log K + K \log(N+M))~