题解：P5490 【模板】扫描线 & 矩形面积并

· · 题解

前置芝士

请务必学透再来做本题。
线段树
离散化

扫描线算法介绍

扫描线算法，专门用于解决多个矩形的面积并问题，算法实现流程跟名字一样。
这是我从 OIwiki 搬运的算法实现过程视频。 通过观察视频，不难发现，计算共分成了 5 个部分，而每个部分的面积，就是一个矩形的面积，直接计算即可（不会的请回到小学再学一次）。
矩形的高可轻易求得，在此不赘述。
现在，重点就是求矩形的底了。再回顾一次视频中扫描方式，可以发现每次扫描到一根线段，我们就会把它加入或者删除。因为每次坐标均为整数，所以可以直接区间加上或者减去 1，最后区间求和即可。
区间加，大家想到什么？线段树对吧。为了加速，考虑使用线段树维护。
在线段树上进行修改，请自行学习，至于树上查询，因为我们需要全部的数量之和，直接查询根节点即可。
整体时间复杂度：O(n\log n)，完全可以通过本题。 :::warning[小提醒] 别忘了离散化！！！
别忘了离散化！！！
别忘了离散化！！！
:::

正确性证明

对于每行：因为每一次当前行中算的是覆盖的部分，重叠的部分只会计算一次，且不重不漏。（因为每次查找的是大于等于 1 的数字个数）。
对于不同行：由于行不同，自然不会产生重叠。

时间复杂度证明

离散化：我采用 sort、unique 和 lower_bound 进行离散化，时间复杂度 O(n\log n)。
区间修改操作：线段树操作，时间复杂度 O(n\log n)。
查询操作：查询总和即可，时间复杂度 O(n)。
总和：省略常数项为 O(n\log n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[3999999],tr[3999999],bj[3999999],lbj[3999999],tot,buc[1008617],len[1008617];
struct nd
{
    int l,r,y,k;
}tree[1008617];
void build(int l,int r,int now)
{
    len[now]=buc[r]-buc[l-1];
    if(l==r)return;
    int mid=l+((r-l)/2);
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
}
void update(int u) 
{ 
    if(lbj[u]>0)tr[u]=len[u];
    else tr[u]=tr[2*u]+tr[2*u+1];
}
void xg(int l,int r,int to,int l1,int r1,int now)
{
    if(l<=l1&&r1<=r)
    {   
        lbj[now]+=to;
        update(now);
        return;
    }
    int mid=l1+(r1-l1)/2;
    if(l<=mid)xg(l,r,to,l1,mid,now*2);
    if(r>mid)xg(l,r,to,mid+1,r1,now*2+1);
    update(now);
}
bool cmp(nd aa,nd bb)
{
    return aa.y<bb.y;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int xl,xr,yl,yr;
        cin>>xl>>yl>>xr>>yr;
        tree[i].l=xl;
        tree[i].r=xr;
        tree[i].y=yl;
        tree[i].k=1ll;
        tree[i+n].l=xl;
        tree[i+n].r=xr;
        tree[i+n].y=yr;
        tree[i+n].k=-1ll;
        buc[++tot]=xl;
        buc[++tot]=xr;
    }
    sort(buc+1,buc+tot+1);
    tot=unique(buc+1,buc+1+tot)-buc-1;
     for(int i=1;i<=2*n;i++) 
    {
        tree[i].l=lower_bound(buc+1,buc+1+tot,tree[i].l)-buc;
        tree[i].r=lower_bound(buc+1,buc+1+tot,tree[i].r)-buc;
    }
    sort(tree+1,tree+1+2*n,cmp);
    build(1,tot,1);
    int ans=0;
    for(int i=1;i<=2*n;i++) 
    {
        ans+=(tree[i].y-tree[i-1].y)*tr[1];
        xg(tree[i].l+1,tree[i].r,tree[i].k,1,tot,1);
    }
    cout<<ans;
    return 0;
}

小练习

别看我，我除了前两题全都不会做……
【模板】离线二维数点
矩形周长
扇形面积并
纵坐标扫描线
洪水