P5490 【模板】扫描线

给你 n 个位于平面直角坐标系上的长方形，它们之间可能互相重叠，求这些长方形的面积。

很显然，对于长方形之间有重叠部分，如果采用容斥原理，不仅非常复杂，而且难以实现。

事实上，既然题目已经给了我们这些长方形的顶点，这些长方形最终构成的图形可以被坐标轴划分为 m 个长方形。

而我们只需要处理这 m 个长方形面积之和即可。

如果我们采用 y轴划分，每一个长方形对最终面积的贡献取决其在 [y1,y2] 这段区间里所占的 x 轴的长度，此时我们所求的，就是所有属于这段区间的 x 的并集。

这时候，扫描线的思路就登场了！引入入边，出边的概念，对这个集合进行维护，入边则添加，出边则删除，采用线段树维护 x 的并集。

由于题目所给数据范围过大，我们需要进行离散化以及采用线段树动态开点操作(很简单的)。

此时，思路已经很清晰了。

上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,t,X1,X2,Y1,Y2,ans;
int x[N<<1];
struct node{
    int l,r,cnt,len;
}tree[N<<2];
struct Line{
    int l,r,h,flag;
    bool operator<(const Line &rhs) const{
        return h<rhs.h;
    }
}line[N<<1];
void push_up(int k){
    if(tree[k].cnt) tree[k].len=(x[tree[k].r+1]-x[tree[k].l]);
    else tree[k].len=tree[k<<1].len+tree[(k<<1)+1].len;
}
void build(int k,int l,int r){
    tree[k].l=l,tree[k].r=r;
    if(l==r){
        tree[k].len=tree[k].cnt=0;return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    push_up(k);
}
void update(int k,int l,int r,int w){
    if(x[tree[k].r+1]<=l||x[tree[k].l]>=r) return;
    if(x[tree[k].l]>=l&&x[tree[k].r+1]<=r){
        tree[k].cnt+=w;
        push_up(k);
        return ;
    }
    int mid=tree[k].l+tree[k].r>>1;
    update(k<<1,l,r,w);
    update(k<<1|1,l,r,w);
    push_up(k);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>X1>>Y1>>X2>>Y2;
        x[2*i-1]=X1;x[2*i]=X2;
        line[2*i-1]={X1,X2,Y1,1};
        line[2*i]={X1,X2,Y2,-1};
    }
    n<<=1;
    sort(line+1,line+n+1);
    sort(x+1,x+1+n);
    m=unique(x+1,x+1+n)-x-1;
    build(1,1,m-1);
    for(int i=1;i<n;++i){
        update(1,line[i].l,line[i].r,line[i].flag);
        ans+=(tree[1].len*(line[i+1].h-line[i].h));
    }
    cout<<ans;
    return 0;
}

526互联

线段树之扫描线

P5490 【模板】扫描线