P5567 [SDOI2008]立方体覆盖

看到题目的描述，就很容易想到扫描线，但是扫描线是二维的，这道题是三维的，怎么办？

我们运用扫描线的思想，将这些立方体分隔成为许多的小立方体（如下图）。我们这样就可以每一次计算小立方体就可以了，每一次我们运用扫描线求出众多矩形的面积并，再乘以横向的长度，就可以求出小体积，再将这些小体积相加，就是答案。

#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);
}