题目描述

A 君近日为准备省队选拔，特意进行了数据结构的专项训练。训练过程中就遇到了“矩形面积并”这道经典问题，即：给出 $N$ 个各边与坐标轴平行（垂直）的矩形，求矩形覆盖的面积之和。A 君按纵坐标建立线段树后按横坐标扫描计算，轻易 AC 了这道题，时间复杂度为 $O(N \log N)$。

为了强化训练，A 君将问题推广到三维空间中，即：给出 $N$ 个各棱与坐标轴平行（垂直）的立方体，求立方体覆盖的体积之和。为了简化问题，令立方体均退化为正立方体，用四元组 $(x, y, z, r)$ 表示一个立方体，其中 $x, y, z$ 为立方体的中心点坐标，$r$ 为中心点到立方体各个面的距离（即立方体高的一半）。

这次可难住了 A 君，只好请你——未来的金牌——来帮助他了。

输入格式

第一行是一个正整数 $N$。

以下 $N$ 行每行四个整数 $x, y, z, r$，由空格隔开。

输出格式

共一个数，即覆盖的总体积。

3
0 0 0 3
1 –1 0 1
19 3 5 6

1944

数据规模与约定

• 对于 $100 \%$ 的数据，$1 \leq N \leq 100$，$-10^3 \leq x, y, z \leq 10^3$，$1 \leq r \leq 200$。

题目来源

没有写明来源