Subtask 1

We can use coordinate compression to reduce the problem to a ~2N \times 2N~ grid where each cell potentially has a different size. Then we can use a 2D prefix sum array to calculate how many rectangles cover each cell. The total area of the union of the rectangles (case where ~M = 0~) can be calculated by iterating over each cell and adding its area if at least one rectangle covers it. For the ~M = 1~ case, we need to calculate for each rectangle how much area we would lose if we removed it. This is the area of the cells it covers that are currently covered by exactly one rectangle. To calculate this efficiently, we can use another 2D prefix sum array that stores the sum of areas of cells that are covered by exactly one rectangle.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 2

For this subtask, we just need the area of the union of the rectangles. This is a classic problem and can be solved by line sweeping and maintaining a lazy propagated segment tree where position stores the number of rectangles at that ~y~ value. Each node in the segment tree will need to store the minimum value in its subtree and the frequency of that value. Then at each ~x~ coordinate, we increase the answer by the number of elements that aren't ~0~.

Time Complexity: ~\mathcal{O}(N \log Y + X)~ where ~X~ and ~Y~ are the maximum ~x~ and ~y~ values contained by rectangles, respectively.

In hindsight, this subtask probably should have been worth fewer points and should have been placed before subtask ~1~ because apparently everyone has seen this kind of problem before.

Subtask 3

It might be tempting to try to use 2D data structures for this subtask. However, the lazy propagation that would be required for a segment tree solution does not extend nicely to 2D. This makes this approach infeasible, or at least, the problem authors have not found an efficient solution using 2D data structures.

The intended solution instead is to line sweep and maintain a one dimensional segment tree. The main operation the segment tree needs to support is the following: if the line sweep currently has ~x~ coordinate ~a~, given two integers ~l~ and ~r~, count the number of cells ~(x, y)~ that are covered by exactly one rectangle and have ~0 \le x \le a~, ~l \le y \le r~. With this operation, we can calculate how many cells would no longer be covered if we remove a rectangle by querying the vertical line corresponding to its left and right boundaries and subtracting them.

Coming up with what values to store at each node and implementing the lazy propagation can also be quite time consuming. The reference solution stores a total of ~11~ integers at each node. These include ~5~ primary values necessary even for querying the tree: the smallest value in the interval, the frequency of that value, the second smallest value in the interval, the frequency of that value, and the total number of cells that interval has swept over that are covered by exactly one rectangle.

For lazy propagation, we know that the interval had its value increased by ~1~ and decreased ~1~ a bunch of times in some order. So we will need to store some information about this sequence of increases and decreases. For the reference solution, we found it useful to store the following ~6~ values to support lazy propagation: initial time (x position of the line sweep) when this lazy propagation started, the final difference of values that this update caused, the time at which this final difference was reached, the lowest difference reached by this update, the amount of time that was spent at the lowest value, and the amount of time that was spent at one larger than the lowest value. The exact details of an implementation will not be provided here.

Time Complexity: ~\mathcal{O}(N \log Y)~

It might also be possible to get an ~\mathcal{O}(N \sqrt{N})~ solution to pass with a similar approach if it has a sufficiently good constant factor.