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

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

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

　　第一行是一个正整数N。

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

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

1944

#include <cstdio>

#include <algorithm>

using namespace std;

#define N 101

#define inf 1000

int n,cnt,idx,root,ans,tot;

int son[3000<<5][2],times[3000<<5],sum[3000<<5];

struct Surface {int x1,y1,x2,y2,z,kind;}surface[N<<5];

bool cmp1(const Surface &a,const Surface &b) {return a.z<b.z;}

struct Line {int x,y1,y2,kind;}line[N<<1];

bool cmp2(const Line &a,const Line &b) {return a.x<b.x;}

void update(int p,int l,int r)

{(times[p])?sum[p]=r-l+1:sum[p]=sum[son[p][0]]+sum[son[p][1]];}

void change(int &p,int l,int r,int x,int y,int delta)

{

	if(!p) p=++cnt;

	if(x<=l&&r<=y) {times[p]+=delta,update(p,l,r);return;}

	int mid=(l+r)>>1;

	if(x<=mid) change(son[p][0],l,mid,x,y,delta);

	if(y>mid) change(son[p][1],mid+1,r,x,y,delta);update(p,l,r);

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);

		surface[++idx].z=c-d,surface[idx].x1=a-d;

		surface[idx].y1=b+d,surface[idx].x2=a+d;

		surface[idx].y2=b-d,surface[idx].kind=1;

		surface[++idx].z=c+d,surface[idx].x1=a-d;

		surface[idx].y1=b+d,surface[idx].x2=a+d;

		surface[idx].y2=b-d,surface[idx].kind=-1;

	}

	sort(surface+1,surface+idx+1,cmp1),surface[idx+1].z=surface[idx].z;

	for(int i=1,tmp=0;i<=idx;tmp=0)

	{

		int area=0;

		while(surface[i].z==surface[i+tmp].z&&i+tmp<=idx) tmp++;

		for(int j=0;j<tmp;j++)

		{

			line[++tot].x=surface[j+i].x1,line[tot].y1=surface[j+i].y2;

			line[tot].y2=surface[j+i].y1-1;

			line[tot].kind=1*surface[i+j].kind;

			line[++tot].x=surface[j+i].x2,line[tot].y1=surface[j+i].y2;

			line[tot].y2=surface[j+i].y1-1;

			line[tot].kind=-1*surface[i+j].kind;

		}sort(line+1,line+tot+1,cmp2);

		for(int j=1,now=0;j<=tot;j+=now,now=0)

		{

			area+=sum[root]*(-line[j-1].x+line[j].x);

			while(line[j+now].x==line[j].x)

				change(root,-inf,inf,line[j+now].y1,line[j+now].y2

					,line[j+now].kind),now++;

		}i+=tmp;

		ans+=area*(surface[i].z-surface[i-1].z);

	}

	printf("%d",ans);

}