Union Area of Axis-Aligned Rectangles

Given n rectangles whose sides are parallel to the coordinate axes, compute the area of their union. In other words, if some regions are covered by more than one rectangle, count them only once.

The problem can be solved using a sweep line algorithm combined with coordinate compression and a segment tree to efficiently update and query the total length of covered intervals along the y-axis. The key idea is to process vertical edges (both left and right) of the rectangles in sorted order and maintain a structure that helps to compute the y-length that is currently covered. The total union area is then the summation of the product of the covered y-length and the difference in x between consecutive events.

The formula for the area can be informally written in LaTeX as:

\( \text{Area} = \sum_{i=1}^{k-1} \text{covered}(x_i) \times (x_{i+1} - x_i) \)

inputFormat

The first line contains an integer n (1 ≤ n).

Each of the next n lines contains four integers x1, y1, x2, y2 which represent the coordinates of the bottom‐left and top‐right corners of a rectangle. It is guaranteed that x1 < x2 and y1 < y2.

outputFormat

Output a single integer representing the union area of the given rectangles.

sample

1
0 0 2 3

6