2292. Area Covered by Rectangles

k axis-aligned rectangles are given, each by its lower-left and upper-right corner. Print the total area covered by at least one of them.

(0,0)-(4,4) and (2,2)-(6,6) -> 28 16 + 16 - 4 overlapping (0,0)-(2,2) and (4,4)-(6,6) -> 8 disjoint

The area here is already a whole number, because every side is an integer and every rectangle's area is a product of two integers, so unlike the rest of this topic there is nothing to double. Boundaries have zero area, so two rectangles that meet only along an edge contribute no overlap, and rectangles may be duplicated.

## What most people try first

Adding the areas and subtracting the pairwise overlaps. That is the first two terms of inclusion-exclusion and it is wrong as soon as three rectangles share a region: the triple overlap is added three times, removed three times, and so ends up counted zero times instead of once. The three-rectangle declared test exists to catch exactly this, and it is worth running the wrong formula on it by hand to see the shortfall.

The full inclusion-exclusion over all 2^k - 1 non-empty subsets is correct and there are 2^k of them, so it stops being usable in the low twenties.

The other reflex is to mark a grid of cells. With coordinates up to 10^6 the grid has 4 * 10^12 cells, so it is not the size of the ANSWER that defeats this, it is the size of the plane.

## Cut the plane into slabs

Collect every x coordinate that appears, as a left or a right edge, sort them and remove duplicates. Between two consecutive values the set of rectangles covering that vertical strip does not change, because a rectangle can only start or stop at one of the collected values. So the plane splits into at most 2k - 1 slabs, and inside a slab the covered region is a union of y intervals that is the same all the way across.

The total is then

sum over slabs of (slab width) * (length of the union of the active y spans)

This is coordinate compression: the coordinates themselves are irrelevant, only the ORDER in which they occur matters, and the slab list is that order made explicit.

## The y union inside a slab, without re-sorting

Sort the rectangles ONCE by their lower y, before the sweep. Then in every slab, walking that fixed order visits the active spans in increasing order of lower endpoint, which is what a merge needs:

cur = none for each rectangle in the y-sorted order skip it unless x1 <= slab_left and x2 >= slab_right if cur is none or y1 > cur_hi start a new run, banking the old one else cur_hi = max(cur_hi, y2) bank the final run

Starting a new run only when y1 > cur_hi, and not when y1 >= cur_hi, is the decision that makes two spans touching at a single y merge into one rather than being counted as two runs with a gap of zero between them. Both give the same total here, because a gap of zero adds nothing, but the strict comparison is the one that matches the statement's rule that boundaries have no area, and it is the one to keep when the same code is reused to count runs rather than measure them.

## Why this is correct

Every point of the covered region lies in exactly one slab, since the slabs partition the x range, and within its slab it lies in the union of the active y spans. So the sum counts each covered point once. Nothing is approximated.

## Width

Coordinates satisfy |x|, |y| <= 1000000, so the whole arrangement sits in a 2 * 10^6 by 2 * 10^6 box and the answer is at most 4 * 10^12. That is far past the 2147483647 a signed 32-bit integer holds, so the accumulator must be 64 bit: a 32 bit accumulator overflows, and a single slab contribution can reach 4 * 10^12 on its own. The value is below 2^53 = 9007199254740992, so a JavaScript Number is exact and no BigInt is needed.

Constraints - `1 <= k <= 1000` - `-1000000 <= x1, y1, x2, y2 <= 1000000` - `x1 < x2` and `y1 < y2`, so every rectangle has positive area - rectangles may overlap, be nested, or be given more than once - the answer can be as large as 4000000000000, which is past the top of a signed 32-bit integer