题意： 给若干个长方体，求出长方体至少相交三次的总体积；
分析：经典扫描线的题，z的范围不高于500，且只有1000个点，可以考虑在外层循环枚举z -500~500，也可以直接类似于扫描线一样，把z存在数组里， 每次算出来相交面积，ans+=z[i+1]-z[i];
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e3+5;
const int inf=0x3f3f3f3f;
#define ls (i<<1)
#define rs (i<<1|1)
struct line
{
int x1,x2,z1,z2,y,flag;
line(){}
line(int t1,int t2,int t3,int t4,int t5,int t6)
{
x1=t1; x2=t2; z1=t3; z2=t4; y=t5; flag=t6;
}
};
struct node
{
int s1,s2,s3,cov;///s1表示覆盖大于等于1的和，s2,s3同理
void clr(){ s1=s2=s3=cov=0; }
};
line a[N<<1],b[N<<1];
node tree[N<<2];
int temp[N<<1],zz[N<<1],n,m;
bool cmp(line p,line q)
{
return p.y<q.y;
}
void pushup(int i,int l,int r)
{
int c=tree[i].cov;
if(c)
{
tree[i].s1=temp[r+1]-temp[l];//若覆盖了，s1=区间长度,temp是离散化的数组
if(c>=2)
{
tree[i].s2=temp[r+1]-temp[l];
if(c>=3) tree[i].s3=temp[r+1]-temp[l];
else if(l==r) tree[i].s3=0;
else tree[i].s3=tree[ls].s1+tree[rs].s1;//若c==2 ,则父亲已经被覆盖了2次，那么只需找儿子覆盖了1次的就行
}
else if(l==r) tree[i].s2=tree[i].s3=0;
else
{
tree[i].s3=tree[ls].s2+tree[rs].s2;//同上
tree[i].s2=tree[ls].s1+tree[rs].s1;
}
}
else if(l==r) tree[i].s1=tree[i].s2=tree[i].s3=0;
else
{
tree[i].s3=tree[ls].s3+tree[rs].s3;
tree[i].s2=tree[ls].s2+tree[rs].s2;
tree[i].s1=tree[ls].s1+tree[rs].s1;
}
}
void build(int i,int l,int r)
{
tree[i].clr();
if(l==r) return;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
void update(int i,int l,int r,int ll,int rr,int v)
{
if(ll<=l&&r<=rr)
{
tree[i].cov+=v;
pushup(i,l,r);
return;
}
int mid=(l+r)>>1;
if(mid>=ll) update(ls,l,mid,ll,rr,v);
if(mid<rr) update(rs,mid+1,r,ll,rr,v);
pushup(i,l,r);
}
int main()
{
int T,test=0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x1,x2,z1,y1,y2,z2;
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
a[i]=line(x1,x2,z1,z2,y1,1);
a[i+n]=line(x1,x2,z1,z2,y2,-1);
temp[i]=x1; temp[i+n]=x2;
zz[i]=z1; zz[i+n]=z2;
}
//排序去重离散化
n<<=1;
sort(a+1,a+n+1,cmp);
sort(temp+1,temp+1+n);
sort(zz+1,zz+n+1);
int k=unique(zz+1,zz+n+1)-zz-1;
m=unique(temp+1,temp+n+1)-temp-1;
for(int i=1;i<=n;i++)
{
a[i].x1=lower_bound(temp+1,temp+m+1,a[i].x1)-temp;
a[i].x2=lower_bound(temp+1,temp+m+1,a[i].x2)-temp;
}
LL ans=0;
for(int i=1;i<k;i++)
{
int tot=0;
build(1,1,m-1);
for(int j=1;j<=n;j++)//选取与z=zz[i]平面相交的立方体，但为了避免重复取，改为左开右闭
{
if(a[j].z1<=zz[i]&&zz[i]<a[j].z2)
b[++tot]=a[j];
}
LL d=zz[i+1]-zz[i];
for(int j=1;j<tot;j++)
{
if(b[j].x1<b[j].x2)
{
update(1,1,m-1,b[j].x1,b[j].x2-1,b[j].flag);
ans+=d*tree[1].s3*(b[j+1].y-b[j].y);
}
}
}
printf("Case %d: %lld
",++test,ans);
}
return 0;
}总结：一道扫描线变形的好题，思维难度不高，但编程细节较多，做这道题的时候WA了很多次，思路没有问题，后面重新写了一道又过了。。。（因果循环，报应不爽）
展望：做一个善良的人，别被坏事缠身。重塑正气，再战心魔！！！