引入
面积并（周长并）
如下图给你一堆矩形求它的面积并或周长并。
显然直接做，就是考虑容斥，但明显不好做。
那就思考如何切割或补，显然补完要减的图形也不规整，只能考虑割。
如何将其割成规整的图形，明显矩形最容易计算和割。
把它割成矩形后发现，每次遇到某个矩形的边就会变，所以考虑一条线从下向上扫，每遇到一个与扫描线平行的边就计算一次答案。
面积并答案为线上被覆盖的长度乘与上一条边的距离。
周长并答案分俩个部分，平行的就是线上被覆盖的长度，垂直的就是线上有多少个端点（在线段内的不算）乘与上一条边的距离。
如何快速维护线上的覆盖长度和有多少段点，显然一个区间修改问题，用线段树。
代码实现
周长并
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,ans,cnt,mx=-100010,mi=100010,las=0;
struct node
{int h,x,y,w;
}bi[N*2];
bool cmp(node x,node y)
{if(x.h==y.h)return x.w>y.w;//先加后减，不让会错
/*
2
0 0 4 4
0 4 4 8
*/return x.h<y.h;
}
struct stu
{int sum;//整个区间被整体覆盖了几次（类似lazytag，但不下传)int num;//整个区间被几条互不相交的线段覆盖int len;//整个区间被覆盖的总长度bool lflag,rflag;
}sh[N*4];
void pushup(int x,int l,int r)
{if(sh[x].sum){sh[x].num=1;sh[x].len=r-l+1;sh[x].lflag=sh[x].rflag=1;}else if(l==r){sh[x].num=0;sh[x].len=0;sh[x].lflag=sh[x].rflag=0;}else {sh[x].num=sh[x<<1].num+sh[x<<1|1].num;if(sh[x<<1].rflag&&sh[x<<1|1].lflag)sh[x].num--;sh[x].len=sh[x<<1].len+sh[x<<1|1].len;sh[x].lflag=sh[x<<1].lflag;sh[x].rflag=sh[x<<1|1].rflag;}
}
void modify(int x,int l,int r,int lt,int rt,int w)
{if(lt<=l&&rt>=r){sh[x].sum+=w;pushup(x,l,r);return ;}int mid=(l+r)>>1;if(lt<=mid)modify(x<<1,l,mid,lt,rt,w);if(rt>mid)modify(x<<1|1,mid+1,r,lt,rt,w);pushup(x,l,r);return;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);bi[++cnt].h=y1,bi[cnt].w=1,bi[cnt].x=x1,bi[cnt].y=x2;bi[++cnt].h=y2,bi[cnt].w=-1,bi[cnt].x=x1,bi[cnt].y=x2;mx=max(mx,x2);mi=min(mi,x1);}if(mi<0){for(int i=1;i<=cnt;i++){bi[i].x+=-mi+1;bi[i].y+=-mi+1;//加一与mx相匹配}mx-=mi;}sort(bi+1,bi+cnt+1,cmp);for(int i=1;i<=cnt;i++){modify(1,mi,mx,bi[i].x,bi[i].y-1,bi[i].w);//减一是因为这是长度为1的叶子的右端点，叶子的编号是左端点即右端点-1.while(bi[i+1].h==bi[i].h&&bi[i+1].w==bi[i].w){i++;modify(1,mi,mx,bi[i].x,bi[i].y-1,bi[i].w);}//同一类型一起处理ans+=abs(sh[1].len-las);//覆盖长度的变化las=sh[1].len;ans+=sh[1].num*2*(bi[i+1].h-bi[i].h);//垂直的边的长度}printf("%d",ans);return 0;
}
面积并
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
#define int long long
int n,ans,xx[N],cnt,mx=1e9+7,mi=0,las=0;
struct node
{int h,x,y,w;
}bi[N*2];
bool cmp(node x,node y)
{return x.h<y.h;
}
struct stu
{int sum;//整个区间被整体覆盖了几次（类似lazytag，但不下传)int len;//整个区间被覆盖的总长度
}sh[N*4];
void pushup(int x,int l,int r)
{if(sh[x].sum)sh[x].len=xx[r+1]-xx[l];else if(l==r)sh[x].len=0;else sh[x].len=sh[x<<1].len+sh[x<<1|1].len;//除了覆盖长度外都不要了
}
void modify(int x,int l,int r,int lt,int rt,int w)
{if(lt<=l&&rt>=r){sh[x].sum+=w;pushup(x,l,r);return ;}int mid=(l+r)>>1;if(lt<=mid)modify(x<<1,l,mid,lt,rt,w);if(rt>mid)modify(x<<1|1,mid+1,r,lt,rt,w);pushup(x,l,r);return;
}
signed main()
{scanf("%lld",&n);for(int i=1;i<=n;i++){int x1,y1,x2,y2;scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);if(x1>x2)swap(x1,x2);if(y1>y2)swap(y1,y2);bi[++cnt].h=y1,bi[cnt].w=1,bi[cnt].x=x1,bi[cnt].y=x2;bi[++cnt].h=y2,bi[cnt].w=-1,bi[cnt].x=x1,bi[cnt].y=x2;mx=max(mx,bi[cnt].y);mi=min(mi,bi[cnt].x);xx[i]=bi[cnt].x;xx[i+n]=bi[cnt].y;}sort(xx+1,xx+2*n+1);int tot=unique(xx+1,xx+2*n+1)-xx-2;sort(bi+1,bi+cnt+1,cmp);for(int i=1;i<=cnt;i++){int x=lower_bound(xx+1,xx+tot+2,bi[i].x)-xx;int y=lower_bound(xx+1,xx+tot+2,bi[i].y)-xx-1;//离散化了modify(1,1,tot,x,y,bi[i].w);ans+=sh[1].len*(bi[i+1].h-bi[i].h);}printf("%lld",ans);return 0;
}
