题意：
贴n张海报（海报的形状是矩形，且每个海报中都去除了一个矩形的区域）问覆盖面积
分析：
把一张海报切换成4个矩形就把问题转化成求4*n个矩阵面积并惹
注意有可能出现空矩阵需要特判
ACcode：
#include <iostream> #include <cstdio> #include <algorithm> #define maxn 50005 #define tmp (st<<1) #define mid ((l+r)>>1) #define lson l,mid,tmp #define rson mid+1,r,tmp|1 #define ll long long using namespace std; int sum[maxn<<2]; int cnt[maxn<<2]; struct Seg{ int l,r,h,s; Seg(){} Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){} bool operator <(const Seg &cmp)const{ return h<cmp.h; } }ss[maxn<<4]; void push_up(int st,int l,int r){ if(cnt[st])sum[st]=r-l+1; else if(l==r)sum[st]=0; else sum[st]=sum[tmp]+sum[tmp|1]; } void update(int L,int R,int c,int l,int r,int st){ if(l>R||r<L)return; if(L<=l&&r<=R){ cnt[st]+=c; push_up(st,l,r); return ; } if(L<=mid)update(L,R,c,lson); if(R>mid)update(L,R,c,rson); push_up(st,l,r); } int main(){ int n,x1,x2,x3,x4,y1,y2,y3,y4,m; while(scanf("%d",&n)&&n){ m=0; for(int i=1;i<=n;++i){ scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4); ss[m++]=Seg(x1,x3,y1,1); ss[m++]=Seg(x1,x3,y2,-1); ss[m++]=Seg(x3,x4,y4,1); ss[m++]=Seg(x3,x4,y2,-1); ss[m++]=Seg(x4,x2,y1,1); ss[m++]=Seg(x4,x2,y2,-1); ss[m++]=Seg(x3,x4,y1,1); ss[m++]=Seg(x3,x4,y3,-1); } sort(ss,ss+m); ll ans=0; for(int i=0;i<m;++i){ update(ss[i].l,ss[i].r-1,ss[i].s,0,50000-1,1); ans+=(ll)sum[1]*(ss[i+1].h-ss[i].h); } printf("%I64d\n",ans); } return 0; }