准备学习扫描线的时候，发现洛谷日报上并没有关于扫描线的文章，于是心血来潮想写一篇。顺便纪念一下我马上结束的 OI 生涯。

本文章同步发布于个人博客。

更好的阅读体验

日志

感谢@许多的帮助纠正。

Upd on 2022/10/23:增加了2道例题

Upd on 2024/7/23：重写部分代码，重写博客导致临时关闭

前置知识

• 线段树或树状数组 （不会的请【模板】线段树 1 ，【模板】树状数组 1 )

• 离散化

目的

先来了解一下扫描线都能做些什么：

• 矩形面积并

• 矩形周长问题

• 二维数点（静态区间查询类问题）

• B 维正交范围

正文

先讲一讲矩形面积并相关问题

先来看一道例题：P5490 【模板】扫描线。

题意：给定 n 个矩形，求这 n 个矩形的并集覆盖的总面积。

众所周知，矩形的面积等于长乘宽，根据这个性质，我们考虑以纵轴为底建立一颗线段树，维护当前的截线段长度，并在枚举下一个点时统计答案，更新截线段长度。可以看成在模拟一条直线，这条直线不断地向右运动，并在移动的时候记录他扫过的矩形面积。

以下面这张图为例：

我们从左向右扫，先扫到下面的位置：

这时候用线段树更新一下目前线段覆盖的范围，然后继续向右扫。

扫描到这个位置时，我们需要将刚才扫过的面积记录到答案中，即上次覆盖的区间范围 \times 移动的距离。并用线段树更新当前覆盖范围，然后继续向右扫描。

每次线段的覆盖面积发生变化时都将当前通过的面积计入答案中，然后用线段树更新现在线段覆盖的区域大小。

重复上述步骤即可。

因为题目中数据范围是 10^9，所以要把矩形的坐标离散化。这时这道题基本上已经解决了。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define N 1000010
#define ls x<<1
#define rs x<<1|1
using namespace std;
int n,sum[N<<3],len[N<<3],vis[N<<3],ans,m,cnt;
int vec[N<<3];
struct node{
    int y1,y2,x,c;
}v[N<<2];
map<int,int> lsh;
bool cmp(node a,node b){
    return a.x<b.x;
}
void update(int x,int l,int r,int L,int R,int data){
    if(r<L||l>R){
        return;
    }
    if(l>=L&&r<=R){
        sum[x]+=data;
    }
    else{
        int mid=(l+r)>>1;
        update(ls,l,mid,L,R,data);
        update(rs,mid+1,r,L,R,data);
    }
    if(sum[x]){
        len[x]=vec[r+1]-vec[l];
    }else{
        len[x]=len[ls]+len[rs];
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        // vec.push_back(y1);vec.push_back(y2);
        vec[++m]=y1,vec[++m]=y2;
        v[++cnt]={y1,y2,x1,1ll};
        v[++cnt]={y1,y2,x2,-1ll};
    }
    sort(vec+1,vec+1+m);
    m=unique(vec+1,vec+1+m)-vec-1;
    for(int i=1;i<=m;i++){
        lsh[vec[i]]=i;
    }
    sort(v+1,v+1+cnt,cmp);
    for(int i=1;i<=cnt;i++){
        update(1,1,m+1,lsh[v[i].y1],lsh[v[i].y2]-1,v[i].c);
        ans+=len[1]*(v[i+1].x-v[i].x);
    }
    printf("%lld",ans);
    return 0;
}

例题

不无聊的序列 Non-boring sequences。

简要题意

如果一个序列的任意一个连续的子序列都有任意一个元素只出现一次，则输出 non-boring，否则输出 boring。

考虑将每个点的权值上次出现的位置 pre_i 和下次出现的位置 sub_i 记录下来，并以 [pre_i+1,i] , [i,sub_i-1] 分别为矩形的长和宽，把他当做一个矩形，并计算最后覆盖的面积总和是否为 \dfrac{n\times (n+1)}{2} 即可。

再来看一个计算矩形周长并的例题：P1856 [IOI1998] [USACO5.5] 矩形周长Picture。

把面积换成周长后这道题毒瘤了十倍。

由于第一篇题解的图画的太好了，我就不献丑了，可以直接看第一篇题解的图。

通过观察题目所给图片以及第一篇题解图片，我们不难发现：纵边总长度 =\sum2\times 被截得的线段条数 \times 当前扫过的高度。

横边总长度 =\sum| 上次截得的总长 - 现在截得的总长 |。

横边总长度也可以用求纵边总长度相同的方法再求一遍。

和面积并相比，周长并中还要维护线段的个数，而且横边和纵边需要分开计算。

由于这题数据比较水，所以不需要离散化，但要注意点的坐标存在负数的情况。

代码如下:

#include<bits/stdc++.h>
#define rg register
using namespace std;
const int MAXN=5010;
const int MAXM=20010;
const int INF=2147483647;
inline int read(){
    int s=0;bool f=false;char c=getchar();
    while(c<'0'||c>'9')f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return (f)?(-s):(s);
}
struct node{
    int l,r,cnt;
    int numx,numy;
    bool lf,rf;
}c[MAXM<<2];
#define lson rt<<1
#define rson rt<<1|1
inline void pushup(int rt){
    if(c[rt].cnt){
        c[rt].numx=c[rt].r-c[rt].l+1;
        c[rt].lf=c[rt].rf=true;
        c[rt].numy=1;
    }
    else if(c[rt].l==c[rt].r){
        c[rt].numx=0;
        c[rt].numy=0;
        c[rt].lf=c[rt].rf=false;
    }
    else{
        c[rt].numx=c[lson].numx+c[rson].numx;
        c[rt].lf=c[lson].lf;
        c[rt].rf=c[rson].rf;
        c[rt].numy=c[lson].numy+c[rson].numy-(c[lson].rf&c[rson].lf);
    }
}
inline void build(int rt,int l,int r){
    c[rt].l=l;
    c[rt].r=r;
    c[rt].cnt=0;
    c[rt].numx=0;
    c[rt].numy=0;
    c[rt].lf=false;
    c[rt].rf=false;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
inline void update(int rt,int l,int r,int v){
    if(l<=c[rt].l&&c[rt].r<=r)
        return c[rt].cnt+=v,pushup(rt);
    int mid=(c[rt].l+c[rt].r)>>1;
    if(l<=mid)update(lson,l,r,v);
    if(r>mid) update(rson,l,r,v);
    pushup(rt);
}
struct edge{int l,r,h,f;}e[MAXN<<1];
bool cmp(edge a,edge b){
    return a.h<b.h||(a.h==b.h&&a.f>b.f);
}
int main(){
    int n=read(),tot=0;
    int maxl=INF,maxr=-INF;
    for(rg int i=1;i<=n;i++){
        int x1=read(),y1=read();
        int x2=read(),y2=read();
        maxl=min(maxl,min(x1,x2));
        maxr=max(maxr,max(x1,x2));
        e[++tot]=(edge){x1,x2,y1,1};
        e[++tot]=(edge){x1,x2,y2,-1};
    }
    sort(e+1,e+tot+1,cmp);
    long long ans=0,last=0;
    build(1,maxl,maxr-1);
    for(rg int i=1;i<=tot;i++){
        update(1,e[i].l,e[i].r-1,e[i].f);
        ans+=labs(c[1].numx-last);
        ans+=(e[i+1].h-e[i].h)*2*c[1].numy;
        last=c[1].numx;
    }
    printf("%lld\n",ans);
    return 0;
}

口胡例题

• 给定一个二维平面，上面有 n 个矩形，m 次询问，每次查询一个二维平面点被多少个矩形覆盖。

做法与上面矩形面积并的做法比较相似，模拟一条线扫描整个平面，并记录当前扫描到的区间被多少个矩形覆盖，这样就把静态的二维问题转换成了动态的一维问题，使用数据结构维护序列，将询问离线化处理，扫描的同时处理出当前的答案并记录下来即可。

扫描线上的数据结构维护的是当前 x 坐标下，每个 y 坐标被多少矩形包含。扫描线进入一个矩形的时候区间 +1，出去的时候区间 -1 即可。

说说 B 维正交范围

B 维正交范围指在一个 B 维直角坐标系下，第 i 维坐标在一个整数范围 [l_i,r_i] 间，内部的点集。

一般来说，一维正交范围简称区间，二维正交范围简称矩形，三维正交范围简称立方体。（后面提到的二维数点就是二维正交范围）

对于一个静态的二维问题，我们可以使用扫描线扫一维，数据结构维护另一维。 在扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询。 如果查询的信息可差分的话直接使用差分，否则需要使用分治。差分一般用树状数组和线段树维护，但因为树状数组好写而且常数小，所以大部分人会选择用树状数组来维护。分治一般是 CDQ 分治（蒟蒻不会CDQ 分治，所以这里不涉及）。

另一种比较容易理解的看待问题的角度是站在序列角度，而不站在二维平面角度。如果我们这样看待问题，则扫描线实际上是枚举了右端点 r=1\cdots n，维护一个数据结构，支持查询对于当前的 r，给定一个值 l，l 到 r 的答案是什么。即扫描线扫询问右端点，数据结构维护所有左端点的答案。

复杂度一般为 \mathcal O((n+m)\log n)。

来看几道例题吧。

口胡例题

给一个长为 n 的序列，有 m 次查询，每次查区间 [l,r] 中值在 [x,y] 内的元素个数。

这个问题就叫做二维数点。我们可以发现等价于我们要查询一个二维平面上矩形内的点的数量和。这里讲一下这个问题最简单的处理方法，扫描线+树状数组。

很显然，这个问题是一个静态的二维问题，我们通过扫描线可以将静态的二维问题转换为动态的一维问题。维护动态的一维问题就使用数据结构维护序列，这里可以使用树状数组。

先将所有的询问离散化，用树状数组维护权值，对于每次询问的 l 和 r，我们在枚举到 l-1 时统计当前位于区间 [x,y] 内的数的数量 a，继续向后枚举，枚举到 r 时统计当前位于区间 [x,y] 内的数的数量 b，b-a 即为该次询问的答案。

可以用我的这道题进行练习。

P1908 逆序对。

没错，逆序对也可以用扫描线的思维来做。考虑将求逆序对的个数转化为从后向前枚举每个位置 i，求在区间 [i+1,n] 中，大小在区间 [0,a_i] 中的点的个数。题目中数据范围为 10^9，很显然要先进行离散化，我们可以考虑从后向前遍历数组，每次遍历到一个数时更新数组数组（线段树），之后统计当前一共有多少个数小于当前枚举的数，因为我们是从后向前遍历的，所以比当前值小的数的个数就是他的逆序对的个数，可以用树状数组或线段树进行单点修改和区间查询。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    ll data;
    ll num;
}f[5000001];
ll n,c[5000001],ans,a[5000001];
bool cmp(node a,node b){
    if(a.data==b.data){
        return a.num<b.num;
    }
    return a.data<b.data;
}
inline ll lowbit(ll i){
    return i&(-i);
}
inline ll sum(ll x){
    ll s=0;
    for(;x>0;x-=lowbit(x)){
        s+=c[x];
    }
    return s;
}

int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>f[i].data;
        f[i].num=i;
    }
    sort(f+1,f+1+n,cmp);
    for(int i=1;i<=n;i++){
        a[f[i].num]=i;
    }
    for(ll i=n;i>0;i--){
        ans+=sum(a[i]);
        for(ll j=a[i];j<=n;j+=lowbit(j)){
            c[j]++;
        }
    }
    cout<<ans;
    return 0;
}

P1972 [SDOI2009] HH的项链

简要题意：给定一个长为 n 的序列，m 次查询区间中有多少不同的数。

这类问题我们可以考虑推导性质，之后使用扫描线枚举所有右端点，数据结构维护每个左端点的答案的方法来实现，我们也可以将问题转换到二维平面上，变为一个矩形查询信息的问题。

在这道题中，对于每个位置 i，考虑预处理出 i 左边离 i 最近的 j 满足 a_i=a_j，用一个数组记录，即 pre_i=j。

然后查询区间中的不同数，我们可以只把每个数在区间中最后一次出现时统计进去。

若这个数在当前区间中是第一次出现，那么这个数肯定满足 pre_i<l。如果不是第一次出现，那么 l \le pre_i。这样问题就转变成了求区间 [l,r] 中，满足 pre_i<l 的 i 的个数。

我们可以考虑差分，将区间 [l,r] 差分为前缀 [1,r] 减去前缀 [1,l-1]。考虑将询问离线处理，假设有一个询问是对于区间 [l,r] 的，我们在 l-1 位置上和 r 位置上分别记录一下，答案为在 r 处记录的 pre_i<l 的个数减去在 l-1 处记录的 pre_i<l 的 i 的个数。

每次查询可以用值域线段树或值域树状数组来维护，注意一个位置上可能有多个询问，但总共的查询次数是 m 次。总时间复杂度 \mathcal O((n+m)\log n)。

代码如下：

#include <bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
#define N 1000010
using namespace std;
struct node{
    int l,r,ans;
}q[N];
struct t{
    int num,s;
};
vector <t> p[N];
int n,a[N],m,now[N];
int siz[N<<2];
void update(int x,int l,int r,int ad){
    if(l==r&&l==ad){
        siz[x]++;
        return;
    }
    int mid=l+r>>1;
    if(ad<=mid){
        update(ls,l,mid,ad);
    }
    else{
        update(rs,mid+1,r,ad);
    }
    siz[x]=siz[ls]+siz[rs];
}
int query(int x,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return siz[x];
    }
    int mid=l+r>>1;
    int res=0;
    if(L<=mid){
        res+=query(ls,l,mid,L,R);
    }
    if(R>mid){
        res+=query(rs,mid+1,r,L,R);
    }
    return res;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        p[l-1].push_back(t{i,-1});
        p[r].push_back(t{i,1});
        q[i]=node{l,r,0};
    }
    for(int i=1;i<=n;i++){
        update(1,0,n,now[a[i]]);
        now[a[i]]=i;
        for(auto x:p[i]){
            int num=x.num;
            q[num].ans+=x.s*query(1,0,n,0,q[num].l-1);
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",q[i].ans);
    }
    return 0;
}

例题

P8593

逆序对的应用。

AcWing 4709. 三元组

上题的弱化版，同样为逆序对的应用。

P8773 [蓝桥杯 2022 省 A] 选数异或

HH 的项链魔改版。

总结

总而言之，扫描线的思路就是数据结构维护一维，暴力模拟另一维。

完结撒花。

萌新第一次写日报，如有错误，希望各位大佬及时指正。

参考资料：

【学习笔记】扫描线 by NCC79601。

扫描线模型 by nzhtl1477。