P5490 [Template] Scanline & Union Area of Rectangles

Find the union area of $n$ rectangles whose sides are parallel to the coordinate axes.

The first line contains a positive integer $n$. The next $n$ lines each contain four non-negative integers $x_1, y_1, x_2, y_2$, indicating that the four vertices of a rectangle are $(x_1, y_1)$, $(x_1, y_2)$, $(x_2, y_2)$, $(x_2, y_1)$.

Output one positive integer in a single line, representing the total area covered by the union of the $n$ rectangles.

For $20\%$ of the testdata, $1 \le n \le 1000$. For $100\%$ of the testdata, $1 \le n \le {10}^5$, $0 \le x_1 < x_2 \le {10}^9$, $0 \le y_1 < y_2 \le {10}^9$. Updated on 4.10 by Dengduck (kouhu) \& yummy (implementation): one more test case was added. Translated by ChatGPT 5