扫描线「模板」

洛谷P5490

题目描述：

求 n 个矩形的面积并。

输入格式：

第一行一个正整数 n
接下来 n 行每行四个非负整数$x1,y1,x2,y2$,表示一个矩形的左下角坐标为$(x1, y1)$,右上角坐标为$(x2,y2)$

输出格式：

一行一个正整数，表示 n 个矩形的并集覆盖的总面积。

输入输出样例

输入 #1

2
100 100 200 200
150 150 250 255

输出 #1

18000

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
vector<int>vec;
const int N = 1e5+10;
struct Segment{
    int x,y1,y2;
    int k;
    bool operator<(const Segment &W)const{
        return x<W.x;
    }
}seg[N*2];
struct Node{
    int l,r,cnt,len;
}tr[N*8];
void build(int u,int l,int r){
    tr[u]={l,r,0,0};
    if(l!=r){
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}
int find(int x){
    return lower_bound(vec.begin(),vec.end(),x)-vec.begin();
}
void pushup(int u){
    if(tr[u].cnt){
        tr[u].len=vec[tr[u].r+1]-vec[tr[u].l];
    }
    else if(tr[u].l!=tr[u].r){
        tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    }
    else tr[u].len=0;
}
void modify(int u,int l,int r,int k){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].cnt+=k;
        pushup(u);
    }
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)modify(u<<1,l,r,k);
        if(r>mid)modify(u<<1|1,l,r,k);
        pushup(u);
    }
}
signed main(){
    int n;
    cin>>n;
    for(int i=1,j=0;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        seg[j++]={x1,y1,y2,1};
        seg[j++]={x2,y1,y2,-1};
        vec.push_back(y1),vec.push_back(y2);
    }
    sort(seg,seg+2*n);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    build(1,0,vec.size()-2);
    int ans=0;
    for(int i=0;i<2*n;i++){
        if(i>0)ans+=tr[1].len*(seg[i].x-seg[i-1].x);
        modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
    }
    cout<<ans<<endl;
    return 0;
}