线段树+扫描线
经典的扫描线问题
首先将一个矩形看作由竖着的两条边和横着的两条边构成
那分成两次考虑，一次考虑竖边，一次考虑横边
首先考虑横边
如图两个矩形，现将横边擦去，留下竖边，将平面划分成3个区域
在代码实现时，可以从左到右记录端点
那么现在想象一条平行于横边的扫描线不断从下往上扫
当扫到一个矩形的下边，将这条矩形的下边包含的区间覆盖
当扫到一个矩形的上边，将这条矩形的上边包含的区间去除覆盖
那么对于这些被竖线划分的区域，建立一棵线段树维护这些区间是否被覆盖
如最底下的矩形下边，覆盖区间2,3
那么如何统计答案
答案就是上一次线段树维护的总区间被覆盖的长度-当前线段树维护的总区间覆盖的长度的绝对值
如上图，扫描到第2边，上一次覆盖2,3，那此处增加为1区间
那么线段树中维护这个区间被完全覆盖的次数和被覆盖的长度即可
#include <iostream> #include <algorithm> #include <map> #include <cstdio> #define inf (int)1e9 using namespace std; int n,w,last,ans; struct node { int a,b,c,d; }p[5100]; struct tree { int l,r,sum; int len; }sh[100000]; struct edge { int l,r,num,kind; }a[11000]; bool cmp(edge a,edge b) { return (a.num<b.num || (a.num==b.num && a.kind>b.kind));//注意如果同一高度的话，先处理下边的 } void pushup(int x) { if (sh[x].sum>0)//如果当前被完全覆盖，那么当前区间被覆盖的长度为r-l+1 sh[x].len=sh[x].r-sh[x].l+1; else if (sh[x].l==sh[x].r)//叶子结点 sh[x].len=0; else sh[x].len=sh[x+x].len+sh[x+x+1].len;//一般情况 } void build(int x,int ll,int rr) { sh[x].l=ll; sh[x].r=rr; sh[x].sum=sh[x].len=0; if (ll==rr) return; int mid; mid=(ll+rr)>>1; build(x+x,ll,mid); build(x+x+1,mid+1,rr); } void change(int x,int ll,int rr,int v) { if (sh[x].l>=ll && sh[x].r<=rr) { sh[x].sum+=v; pushup(x); return; } int mid; mid=(sh[x].l+sh[x].r)>>1; if (ll<=mid) change(x+x,ll,rr,v); if (rr>mid) change(x+x+1,ll,rr,v); pushup(x); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d); for (int i=1;i<=n;i++)//记录前扫描线要扫到的边 { w++; a[w].l=p[i].a;a[w].r=p[i].c; a[w].kind=1;a[w].num=p[i].b;//下边 w++; a[w].l=p[i].a;a[w].r=p[i].c; a[w].kind=-1;a[w].num=p[i].d;//上边 } build(1,-10000,10000); sort(a+1,a+1+w,cmp); last=0;//上一次答案 for (int i=1;i<=w;i++) { change(1,a[i].l,a[i].r-1,a[i].kind); ans+=abs(last-sh[1].len); last=sh[1].len; } w=0;//处理竖边 for (int i=1;i<=n;i++) { w++; a[w].l=p[i].b;a[w].r=p[i].d; a[w].kind=1;a[w].num=p[i].a; w++; a[w].l=p[i].b;a[w].r=p[i].d; a[w].kind=-1;a[w].num=p[i].c; } build(1,-10000,10000); sort(a+1,a+1+w,cmp); last=0; for (int i=1;i<=w;i++) { change(1,a[i].l,a[i].r-1,a[i].kind); ans+=abs(last-sh[1].len); last=sh[1].len; } printf("%d ",ans); }