一、前言
二、扫描线
就是维护矩形的面积/周长并。
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; }