前言

扫描线也不算是一个很冷门的算法吧，但是实现的时候还是稍微有点问题，这里就稍作分析

正文

扫面线开幕雷击

扫描线一般用于解决图形面积、周长等问题，最典型的应用就是处理矩形面积并、周长并类问题

矩形面积并

题面一般是这样的：

求 $n$ 个矩形的面积并，每个矩形以左下角 $(x_1,y_1)$ 和右上角 $(x_2,y_2)$ 的形式给出

有些时候坐标还不是整数，当然啦，这些都不是问题

来康康下面的例子

有效面积为：

那么我们是不是可以按照小学数学方法——割补法来求，按照 $x$ 的顺序从左到右割成若干个矩形，然后从左到右像扫描一样依次求解，这就叫做扫描线

根据 $x$ 值的不同，我们可以把这个平面图形切成好几部分，每一部分都可以看做规则的矩形来求解，而矩形的长 $a$ 是显然的，为两条线相邻 $x$ 的差，关键在于如何维护矩形的宽 $b$，也就是 $y$

上图以第一、二条线为例，$a=3-1=2,b=(6-3)+(2-1)=4$

如图由于每条线段的含义不同，分为 $+1$ 和 $-1$ 两种，通过差分来表示某段 $y$ 区间被覆盖的次数，由此可以得知 $b$，即有效的 $y$ 区间大小。其实维护点是没有意义的，因为会出现点太多和点在实数范围的情况，实际上，对于一条线段来说，左右端点之间的点本质是相同的，我们只需要维护区间即可

就比如上图中 $A,B,C,D$ 四点所在的直线，我们可以看成由四个点分出的五个部分来维护。简而言之，我们不维护点，而是将每个点离散化后维护两点之间的区间

p[++t]=ly,p[++t]=ry;//所有y值一起离散，就好像上图A和E之间也应有一段区间
sort(p+1,p+t+1),t=unique(p+1,p+t+1)-p-1;

比较难以理解的就是用线段树实现部分

tag[k] 维护的是差分数组，f[k] 表示有效 $y$ 值，也就是 $b$

inline void Update(rint k,rint l,rint r) {
    if(tag[k]) f[k]=p[r+1]-p[l];//表示这段区间都被覆盖了，则b为这段区间的长度，r+1是因为端点原因
    else if(l==r) f[k]=0;//一个点无法构成区间，为0
    else f[k]=f[k<<1]+f[k<<1|1];//否则从儿子处更新
}
inline void Modify(rint k,rint l,rint r,rint op) {//op=+1/-1，表示当前线段类型
    if(r<L||R<l) return;//[L,R]表示修改区间
    if(L<=l&&r<=R) {tag[k]+=op;return Update(k,l,r);}
    rint m=(l+r)>>1,ls=k<<1;
    Modify(ls,l,m,op),Modify(ls|1,m+1,r,op),
    Update(k,l,r);
}

直接这样打标记会不会出什么问题？

确实，这样我们就不能查询任意一个区间，然而扫描线查询的是所有区间的总和，也就是 f[1]，因此不会出问题，我们可以讨论一下

设 $k$ 为当前区间，$ls$ 表示当前区间的左子区间，$ls|1$ 为右子区间，就和线段树一样哈

讨论覆盖的情况

  1. 假设 $k$ 没有被覆盖
    那么覆盖了 $k$ 的子区间之后，f[k] 会从 f[ls]&f[ls|1] 处更新，结果是正确的
  2. 假设 $k$ 被覆盖了
    那么覆盖 $k$ 的子区间对 $k$ 是没有影响的，f[k] 由自身的区间长度决定

然后我们就可以得知 f[1] 是肯定正确的，emmm，感觉这证明好像没有什么用

讨论覆盖和删除并存情况

按照平常肯定是会出问题的，但是，矩形有个优美的性质：对边平行且相等，有覆盖肯定有删除，不会出错，因此直接写成上述那样是没问题的

来康康主函数咋写

int main() {
    int i,x,y;n=read();
    for(i=1;i<=n;i++) {//x,L,y,R分别是x1,y1,x2,y2
        x=read(),L=read(),y=read(),R=read(),
        p[++t]=L,b[t]=seg(x,L,R,1),
        p[++t]=R,b[t]=seg(y,L,R,-1);//存线段
    }n<<=1;
    sort(b+1,b+n+1,cmp),sort(p+1,p+t+1);//b数组按照x排序，p是y的数组用于离散化
    t=unique(p+1,p+t+1)-p-1;//去重
    R=lower_bound(p+1,p+t+1,b[1].r)-p-1,//得到区间的离散值，记得端点和区间的区别
    L=lower_bound(p+1,p+t+1,b[1].l)-p,Modify(1,1,t,b[1].op);
    for(i=2;i<=n;i++) {
        ans+=(LL)(b[i].p-b[i-1].p)*f[1];//b[i].p-b[i-1].p=a,f[1]=b
        L=lower_bound(p+1,p+t+1,b[i].l)-p,
        R=lower_bound(p+1,p+t+1,b[i].r)-p-1,
        Modify(1,1,t,b[i].op);
    }printf("%lld",ans);
    return 0;
}

扫描线还是比较单纯的 除了会打出炒面线、草苗线、扫面线之外

Code

Luogu P5490 【模板】扫描线

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct seg{//线段
    int p,l,r,op;
    seg(rint a,rint b,rint c,rint d):p(a),l(b),r(c),op(d){}
    seg(){}
}b[N<<1];
int n,f[N<<3],tag[N<<3],p[N<<1],L,R,t;//注意数组大小
LL ans;
inline void Update(rint k,rint l,rint r) {
    if(tag[k]) f[k]=p[r+1]-p[l];
    else if(l==r) f[k]=0;
    else f[k]=f[k<<1]+f[k<<1|1];
}
inline void Modify(rint k,rint l,rint r,rint op) {
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {tag[k]+=op;return Update(k,l,r);}
    rint m=(l+r)>>1,ls=k<<1;
    Modify(ls,l,m,op),Modify(ls|1,m+1,r,op),
    Update(k,l,r);
}
inline bool cmp(rgt seg a,rgt seg b) {//按照x排序扫描
    return a.p<b.p;
}
int main() {
    rint i,x,y;n=read();
    for(i=1;i<=n;i++) {
        x=read(),L=read(),y=read(),R=read(),
        p[++t]=L,b[t]=seg(x,L,R,1),
        p[++t]=R,b[t]=seg(y,L,R,-1);
    }n<<=1;
    sort(b+1,b+n+1,cmp),sort(p+1,p+t+1);
    t=unique(p+1,p+t+1)-p-1;
    R=lower_bound(p+1,p+t+1,b[1].r)-p-1,
    L=lower_bound(p+1,p+t+1,b[1].l)-p,Modify(1,1,t,1);
    for(i=2;i<=n;i++) {
        ans+=(LL)(b[i].p-b[i-1].p)*f[1];//b[i].p-b[i-1].p=a,f[1]=b
        L=lower_bound(p+1,p+t+1,b[i].l)-p,
        R=lower_bound(p+1,p+t+1,b[i].r)-p-1,
        Modify(1,1,t,b[i].op);//修改
    }printf("%lld",ans);
    return 0;
}

矩形周长并

矩形周长并的思路和面积并类似，也是通过扫描线一条一条进行处理

来看如下例子：

可以看出，原本矩形的边会互相影响，并且多个矩形构成的新图形可能内部是空的

当然了，这些问题扫描线都可以处理

依旧按照上述方法，从左往右扫描

计算平行于 y 轴的边长

平行于 $y$ 轴的边长可以看成是在 $y$ 轴上覆盖区间长度，每扫一条线，$y$ 轴上覆盖的区间就会变化，而这个变化的大小就是有效的边长长度

用 f[1] 表示用线段树维护的在 $y$ 轴上的覆盖区间大小

例如从 1 过渡到了 2，f[1] 从 $2$ 变成了 $4$，那么有效的边长就为 $abs(4-2)=2,ans=0+2=2$，

从 3-4，f[1] 从 $5\to6$，有效边长为 $1,ans=5+1=6$，

从 4-5，f[1] 从 $6\to5$，有效边长为 $abs(5-6)=1,ans=6+1=7$，

从 7-8，f[1] 从 $6\to6$，无变化，

但是如果我们把扫描的顺序换一下，变成 8-7，f[1] 从 $1\to 6$，$abs(1-6)=5$，然而有效边长实际上为 $0$，这就出现了问题

因此我们需要在排序的时候把 $x$ 轴坐标相同的，按照 $op$ 类型排序，先 $+1$ 后 $-1$

struct seg{
    int p,l,r,op;
    seg(rint a,rint b,rint c,rint d):p(a),l(b),r(c),op(d){}
    seg(){}
    inline bool operator< (const seg x) const{
        return (p!=x.p)?p<x.p:op>x.op;
    }
}

同时不要忘记第一次扫描所带来的有效边长

计算平行于 x 轴的边长

如果按照从左到右处理的话，两次扫描之间的 $x$ 坐标的差值是很容易得出的，需要知道的就是在这两次扫描之间平行于 $x$ 轴的线段的数目，显然，这个只需要维护 $y$ 轴覆盖区间形成的线段数即可

这就需要我们多记录几个值，bool fl[k],fr[k] 分别表示左右端点是否被覆盖，int g[k] 表示线段数

$Update()$ 还是比较容易理解的，就不再赘述，其余部分什么多大区别

inline void Update(rint k,rint l,rint r) {
    if(tag[k]) f[k]=p[r+1]-p[l],g[k]=fl[k]=fr[k]=1;
    else if(l==r) f[k]=g[k]=fl[k]=fr[k]=0;
    else {
        rint ls=k<<1;
        f[k]=f[ls]+f[ls|1],
        g[k]=g[ls]+g[ls|1]-(fr[ls]&&fl[ls|1]),
        fl[k]=fl[ls],fr[k]=fr[ls|1];
    }
}

当然我们还可以纵向扫描啊，也就是再做一次类似平行 $y$ 轴的操作，至于码量嘛，这个你自己好好思考一下谁更优秀

最后还需要注意，每条线段有两个端点

Code

Luogu P1856 [USACO5.5]矩形周长Picture

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 5003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0,p=1;
    rgt char c=getchar();
    while(!isdigit(c)) {if(c=='-') p=-1;c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s*p;
}
struct seg{
    int p,l,r,op;
    seg(rint a,rint b,rint c,rint d):p(a),l(b),r(c),op(d){}
    seg(){}
    inline bool operator< (const seg x) const{
        return (p!=x.p)?p<x.p:op>x.op;
    }
}b[N<<1];
int n,L,R,p[N<<1],t,c,ans;
int f[N<<3],g[N<<3],tag[N<<3];
bool fl[N<<3],fr[N<<3];
inline void Update(rint k,rint l,rint r) {
    if(tag[k]) f[k]=p[r+1]-p[l],g[k]=fl[k]=fr[k]=1;
    else if(l==r) f[k]=g[k]=fl[k]=fr[k]=0;
    else {
        rint ls=k<<1;
        f[k]=f[ls]+f[ls|1],
        g[k]=g[ls]+g[ls|1]-(fr[ls]&&fl[ls|1]),
        fl[k]=fl[ls],fr[k]=fr[ls|1];
    }
}
inline void Modify(rint k,rint l,rint r,rint op) {
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {tag[k]+=op;return Update(k,l,r);}
    rint m=(l+r)>>1,ls=k<<1;
    Modify(ls,l,m,op),Modify(ls|1,m+1,r,op),
    Update(k,l,r);
}
int main()
{
    rint i,x,y;n=read();
    for(i=1;i<=n;i++) {
        x=read(),L=read(),y=read(),R=read(),
        p[++t]=L,b[t]=seg(x,L,R,1),
        p[++t]=R,b[t]=seg(y,L,R,-1);
    }n<<=1;
    sort(b+1,b+t+1),sort(p+1,p+t+1);
    t=unique(p+1,p+t+1)-p-1,
    R=lower_bound(p+1,p+t+1,b[1].r)-p-1,
    L=lower_bound(p+1,p+t+1,b[1].l)-p,
    Modify(1,1,t,1),ans=c=f[1];//第一次扫描的有效长度
    for(i=2;i<=n;i++) {
        ans+=2*g[1]*(b[i].p-b[i-1].p),
        L=lower_bound(p+1,p+t+1,b[i].l)-p,
        R=lower_bound(p+1,p+t+1,b[i].r)-p-1,
        Modify(1,1,t,b[i].op),ans+=abs(f[1]-c),c=f[1];
    }printf("%lld",ans);
    return 0;
}

Problem List

devil.