Editorial for BPC 1 S6 - Painters - Olympiads Online Judge

Editorial for BPC 1 S6 - Painters

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: BalintR

Subtask 1

We can use coordinate compression to reduce the problem to a $2N \times 2N$ ~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$ ~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$ ~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)$ ~\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$ ~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$ ~x~ coordinate, we increase the answer by the number of elements that aren't $0$ ~0~.

Time Complexity: $\mathcal{O}(N \log Y + X)$ ~\mathcal{O}(N \log Y + X)~ where $X$ ~X~ and $Y$ ~Y~ are the maximum $x$ ~x~ and $y$ ~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$ ~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$ ~x~ coordinate $a$ ~a~, given two integers $l$ ~l~ and $r$ ~r~, count the number of cells $(x, y)$ ~(x, y)~ that are covered by exactly one rectangle and have $0 \le x \le a$ ~0 \le x \le a~, $l \le y \le r$ ~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$ ~11~ integers at each node. These include $5$ ~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$ ~1~ and decreased $1$ ~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$ ~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)$ ~\mathcal{O}(N \log Y)~

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

Comments

4

brunovsky commented on June 22, 2022, 5:23 a.m. ← edited →

My solution used consumed propagation: when the sweep advances by $\triangle x$ ~\triangle x~, add $\triangle x$ ~\triangle x~ to the root of the segtree as a consumable additive lazy tag. When adding $\triangle x$ ~\triangle x~ to a segtree node $v$ ~v~ with $c\geq 0$ ~c\geq 0~ rectangles stored there: If $c=0$ ~c=0~ we simply store it at $v$ ~v~ to propagate it down later, as usual. If $c\geq 2$ ~c\geq 2~ then it has been determined that an area of $\triangle x\cdot \text{height}(v)$ ~\triangle x\cdot \text{height}(v)~, not necessarily contiguous, was painted by at least the $c$ ~c~ rectangles stored at $v$ ~v~. If $c=1$ ~c=1~ and $i$ ~i~ is the only rectangle at $v$ ~v~, it has been determined that an area of $\triangle x\cdot \text{height}(v)$ ~\triangle x\cdot \text{height}(v)~ was painted by at least $i$ ~i~, and an area $\triangle x\cdot\text{empty}(v)$ ~\triangle x\cdot\text{empty}(v)~ was painted only by $i$ ~i~, where $\text{empty}(v)$ ~\text{empty}(v)~ is the "empty" space in the subtree $v$ ~v~, not occupied by other rectangles, which is just a simple aggregate. This requires storing the rectangles at maximal segtree nodes, which is $\mathcal{O}(n\log n)$ ~\mathcal{O}(n\log n)~ memory.

6

ecnerwal commented on June 22, 2022, 3:34 p.m.

You don't need to store the full list of rectangles at each node; you can store only the xor/sum of their indices, since we only need to look up the rectangle ID if it's the unique one present.