扫描线
用离散线段树实现
时间复杂度\(O(n \log n)\)
P5490 【模板】扫描线
代码
#include <bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
#define lson l,mid,rt<<1
#define rson mid,r,rt<<1|1
#define int long long
const int maxn=2e5+10;
int n,y[maxn*2],ans;
struct tree{
int l,r,len,cnt=0;
}tr[maxn*8];//pushup会多一层
struct Line{
int x,y1,y2,flag;
bool operator <(const Line &rhs) const{
return x<rhs.x;
}
}L[maxn*2];
void pushup(int rt){
if(tr[rt].cnt>0) tr[rt].len=tr[rt].r-tr[rt].l;
else tr[rt].len=tr[rt<<1].len+tr[rt<<1|1].len;
}
void build(int l,int r,int rt){
tr[rt].l=y[l],tr[rt].r=y[r];
if(r==l+1) return ;//叶子结点长度是2
build(lson);build(rson);
}
void update(int rt,int a,int b,int cnt){
if(a>=tr[rt].r||b<=tr[rt].l) return;
if(a<=tr[rt].l&&b>=tr[rt].r){
tr[rt].cnt+=cnt;pushup(rt);
return;
}
update(rt<<1,a,b,cnt);update(rt<<1|1,a,b,cnt);
pushup(rt);
}
signed main(){
/*2023.5.3 hewanying P5490 【模板】扫描线 扫描线*/
scanf("%lld",&n);
for(int i=1;i<=n;i++){
int X1,X2,Y1,Y2;
scanf("%lld%lld%lld%lld",&X1,&Y1,&X2,&Y2);
L[i]=(Line){X1,Y1,Y2,1};L[i+n]=(Line){X2,Y1,Y2,-1};
y[i]=Y1;y[i+n]=Y2;
}
n*=2;
sort(L+1,L+n+1);sort(y+1,y+n+1);
build(1,n,1);
for(int i=1;i<n;i++){
update(1,L[i].y1,L[i].y2,L[i].flag);
ans+=(L[i+1].x-L[i].x)*tr[1].len;
}
printf("%lld\n",ans);
return 0;
}