一、前言
二、扫描线
就是维护矩形的面积/周长并。
1.面积并
用一条线从下往上扫，将所有矩形变成一片一片的 ( 感性理解 ) ，容易知道最多 2*n-1 片，每片的贡献是 当前线段总长度*这片的厚度。
最多 2*n 条竖直的线，所以最多 2*n 个端点，最多 2*n-1 个区间。
离散化后计算出不同端点的个数 cnt 。线段树上 [l,r] 的区间代表实际上第 l 个端点到第 r+1 个端点。维护每一个区间的长度。
时间复杂度：O(nlogn)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f?x:-x;
}
ll ans=0;
int n,t[2000010],p[2000010],q[2000010],u[2000010],cnt;
struct scl{
int l,r,x,h;//区间的左端点、右端点、纵坐标、这条边是矩形的下边(h=1)还是上边(h=-1)
}s[500010];
bool cmp(scl _1,scl _2){//按照纵坐标排好序
return _1.x<_2.x;
}
void modify(int x,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
p[x]+=v;//区间被覆盖的次数
t[x]=p[x]?(q[r+1]-q[l]):(t[x<<1]+t[x<<1|1]);//如果区间被完全覆盖了≥1次，该区间的线段长度就是区间总长；
return;
}
int mid=(l+r)>>1;
if(ql<=mid)modify(x<<1,l,mid,ql,qr,v);
if(qr>mid)modify(x<<1|1,mid+1,r,ql,qr,v);
t[x]=p[x]?(q[r+1]-q[l]):(t[x<<1]+t[x<<1|1]);
}
int main(){
n=read();
for(int i=1,a,b,c,d;i<=n;i++){
a=read();b=read();c=read();d=read();
s[(i<<1)-1]=scl{a,c,b,1};
s[i<<1]=scl{a,c,d,-1};
q[(i<<1)-1]=a;q[i<<1]=c;//q 数组用于存储区间端点以方便进行离散化
}
sort(q+1,q+2*n+1);
cnt=unique(q+1,q+2*n+1)-q-1;
sort(s+1,s+2*n+1,cmp);
for(int i=1,x,y;i<2*n;i++){
x=lower_bound(q+1,q+cnt+1,s[i].l)-q;
y=lower_bound(q+1,q+cnt+1,s[i].r)-q;
modify(1,1,cnt-1,x,y-1,s[i].h);
ans+=1ll*t[1]*(s[i+1].x-s[i].x);
}
cout<<ans<<'\n';
return 0;
}