P5567 [SDOI2008] Cube Coverage

Recently, Mr. A has been doing special training on data structures to prepare for the NOI Qualifier team selection. During the training, he encountered the classic problem “Union Area of Rectangles”: given $N$ rectangles whose sides are parallel (perpendicular) to the coordinate axes, find the total area covered by these rectangles. Mr. A built a segment tree along the $y$-axis and then used a sweep line along the $x$-axis to compute it, easily getting AC, with time complexity $O(N\log N)$. To further strengthen the training, Mr. A extended the problem to three-dimensional space: given $N$ cubes whose edges are parallel (perpendicular) to the coordinate axes, find the total volume covered by these cubes. To simplify the problem, assume all cubes are axis-aligned regular cubes. Use a quadruple $(x, y, z, r)$ to represent a cube, where $x, y, z$ are the coordinates of the cube’s center, and $r$ is the distance from the center to each face of the cube (i.e. half of the cube’s side length). This time Mr. A got stuck, so he asks you—the future gold medalist—to help him.

The first line contains a positive integer $N$. The next $N$ lines each contain four integers $x, y, z, r$.

Output the total covered volume.

Constraints: $N \leq 100, -1000 \leq x,y,z \leq 1000, r \leq 200$. Translated by ChatGPT 5