Mars Map

In 2051, the ambitiously launched Mars probe Seonghwa sent back N maps of the regions it surveyed.

Encouraged by the probe's success, the space agency announced an ambitious plan to complete a map of the entire surface of Mars.

Before building the full map, all of the maps the probe has sent so far were overlaid and merged into one. What is the area of the region actually covered by this merged map?

Each map sent by the probe is always an axis-aligned rectangle, and the maps may overlap.

The first line contains the number of maps N (1 ≤ N ≤ 10,000) sent by the probe.

Each of the next N lines describes one map with four integers x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000). (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner of the rectangle. Every rectangle's sides are parallel to the x-axis or the y-axis.

Print, on the first line, the total area of the region covered when all maps sent so far are overlaid and merged together.

This asks for the area of the union of several rectangles. Sweeping a vertical line across the x-axis, together with coordinate compression on the y values and a segment tree, solves it in O(N log N).