扫描线

Larrylai · 2026-07-23 20:46:59 · 算法·理论

扫描线

背景

今天的学习计划是扫描线，在刚开始打开 51goc 时，看到这个算法（个人认为是一种分割的思想），心想：“这啥呀，听都没听过。”进去一看讲义，没有讲义，有的只是一道道题的解析。没办法，只好打开 oi-wiki，还是看不懂。

正文

kw 首先问了我们一个问题：数轴上有 n 条线段，求至少被一条线段覆盖的总长度。这题很简单，简单的可以用前缀和，容斥，差分；难一点的可以用线段树。但如果这个问题上升到二维呢？如这题，用暴力去枚举每个点是否被覆盖，当 n=10^5 时会 TLE。这时候可以先画图，将一个个线当作分割线，详细可见 这篇文章，到了这里，会想到这不就是小学求面积割补法中的割吗？回到 OI 中，我们依旧要把二维转化成一维，或者说是用一维的办法带到二维中去，看一下行不行得通。

难点

在二维中，随着扫描线的移动，“被覆盖的纵轴区间”在每条竖线上完全不同，矩阵的上下边缘参差不齐。但与此同时，矩阵都轴对齐的图形，不难发现：

1. 所有的矩阵中的左右两边都是竖直线段.
2. 只有当扫描线经过某一个矩阵的边缘是，“被覆盖的纵轴区间”才会发生变化。
3. 相邻两条边之间，被覆盖的纵轴区间”是不变的。由此我们可以得到：面积 = 覆盖长度 \times (下一个 x − 当前 x)。那么此时，问题就变成了在扫描的过程中，如何维护 y 轴的“被覆盖长度”。

算法的诞生

我们可以对每一个矩形定义两条边：

入边（矩阵的左边缘）：在 x=x1 处，y 轴上的区间 [y1,y2] 被加入覆盖。记 v=1。

出边（矩阵的右边缘）：在 x=x2 处，y 轴上的区间 [y1,y2] 被移除覆盖。记 v=-1。

现在问题变成了一个一维动态问题：轴上不断有“区间加 +1”（入边）和“区间加 -1”（出边）的操作。

每次操作后，我们需要知道“至少被覆盖一次的总长度”。

由此，我们可以想到线段树。但是，跟线段树还是有写关键的区别：线段树是区间加，查询该区间的总和或最值。而本题是动态维护全局“被覆盖次数 \ge 1 的区间总长”。

tip：由于 y 坐标的范围可以达到 10^9,所以这里要用离散化优化一下。

在我们用线段树去做维护这个区间时，我们不需要懒标记，这是为什么呢？因为在维护的过程中，我们不需要下放 cnt，因为我们只查询根节点的长度且入边和出边天生配对，一正一负终究会被抵消。

复杂度

总的时间复杂度为 O(n \log n)。

空间复杂度总共为 O(n)。

总结

今天学习的这一个思想在刚开始会很抽象，但是在学完之后会有一种降维打击的感觉，在二维的题里用一维的思路做。特别是在后面做题的过程中，其实思路是好想的 （除了建图），就是难打。用 kw 的话说就是太肉了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=100005;
int T,n,m,ans;
vector<int> ys;
int cnt[MAXN<<3],raw[MAXN<<1],len[MAXN<<3];
struct edge{
    int x,y1,y2,v;
    bool operator<(const edge &e) const {
        return x<e.x;
    }
}e[MAXN<<1];
void pushup(int p,int l,int r){
    if(cnt[p])
        len[p]=raw[r+1]-raw[l]; // 当前区间被完全覆盖
    else if(l==r)
        len[p]=0; // 叶子节点且未被覆盖
    else
        len[p]=len[p<<1]+len[p<<1|1];// 由子节点合并
}
void update(int p,int l,int r,int ql,int qr,int v){
    if(ql<=l && r<=qr){
        cnt[p]+=v;
        pushup(p,l,r);
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid)
        update(p<<1,l,mid,ql,qr,v);
    if(qr>mid)
        update(p<<1|1,mid+1,r,ql,qr,v);
    pushup(p,l,r);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y,x2,y2;
        cin>>x>>y>>x2>>y2;
        e[(i<<1)-1]={x,y,y2,1};//入边
        e[i<<1]={x2,y,y2,-1};//出边
        ys.push_back(y);
        ys.push_back(y2);
    }
  //离散化
    sort(ys.begin(),ys.end());
    ys.erase(unique(ys.begin(),ys.end()),ys.end());
    for(int i=0;i<ys.size();i++)
        raw[i+1]=ys[i];
    m=ys.size();
    sort(e+1,e+(n<<1)+1);
    for(int i=1;i<(n<<1);i++){
        edge &  u=e[i];
        int xb1=lower_bound(raw+1,raw+m+1,u.y1)-raw;
        int xb2=lower_bound(raw+1,raw+m+1,u.y2)-raw;
        update(1,1,m-1,xb1,xb2-1,u.v);// 注意：线段树维护的是“段”，[y1, y2] 对应的是第 xb1 段到第 xb2-1 段
        ans+=len[1]*(e[i+1].x-u.x);
    }
    cout<<ans;
    return 0;
}

番外

在 万恶的项链 这题中，第一眼想到的是用莫队去做，毕竟是求区间内不同数字的个数，交了一发后发现只有 70 pts，仔细想了一下莫队的时间复杂度为 O((n+m) \sqrt n)，10^6 会超时。

回到正解，这题其实跟 这一题 挺像的，都是求区间内的问题。唯一不同的是第二题要满足两个条件：