扫描线专题

Zskioaert1106 · 2025-06-22 09:22:20 · 算法·理论

前置知识：离散化

离散化是一种缩减数据值域的办法。

对于一组数据 \{100,99,2,1,114514\}，我们想要以它们为下标建立线段树，同时区间端点只会是这 5 个数，则我们可以将它们映射成：\{4,3,2,1,5\}，保证相对大小不变，再维护每段元线段的实际长度，则可以在支持原操作的情况下，将空间复杂度由通常是 10^9 的值域缩减到 O(n)。

具体操作方法：先将原数组排序后去重，新数组中元素的下标就是原数组的映射。

我们可以使用 algorithm 头文件中的相关函数来方便快捷地离散化：

sort(c+1,c+1+n); // 排序，c 是需要离散化的数组，但通常我们会将其复制一份
int tot=unique(c+1,c+1+n)-(c+1); // 去重，tot 就是离散化后的值域了

题目引入：矩形面积并

P5490：给出 n 个边平行于坐标轴的矩形的位置，求它们覆盖的总面积。n \le 10^5,x,y \le 10^9。

第一步肯定是将坐标离散化，从而将值域缩减到 [1,2n]。接下来最显然的方法就是建一个二维 bool 数组，统计最终有多少面积被覆盖过。这类实现中，最优的时空复杂度为 O(n^2)，如果你已经学过差分，你可以去 AC 这道题，其数据范围为 n \le 10^4。

算法介绍

扫描线是一种算法策略，其大概的思想就是处理高于一维的空间问题时，遍历其中的一维，用数据结构等对其它维进行维护。其典型应用之一就是二维正交范围问题，也就是上面的矩形面积并。

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

通常来讲，一维正交范围称为区间，二维正交范围称为矩形，三维正交范围称为立方体。

对于本题，我们想象有一条直线 l:y=i 在从下往上扫描。那么，我们只要求出所有时刻 l 上有矩形覆盖的位置总长度之和，就能解决矩形覆盖的总面积了。

例题解决：矩形面积并

我们把每个矩形拆成两条线段，一条是矩形的下边，将它赋权为 1，表示有一个矩形开始与扫描线相交；一条是矩形的上边，赋权 -1，表示有一个矩形离开了扫描线。可见每条线段有 4 个信息：纵坐标 y、左右端点 x_1,x_2 以及权值。

又因为纵坐标相邻的两条线段之间，扫描线的总覆盖长度一定不会有任何变化，所以我们的扫描线只需要遍历所有矩形的上下边纵坐标 y_1,y_2 组成的集合就行。这样，在离散化后，我们遍历 y 这一维的时间复杂度就控制在 O(n) 了。

接下来考虑如何快速维护扫描线上被覆盖的位置。发现遍历到每条线段都形如区间加/减，于是自然想到线段树。同理，同一时刻横坐标相邻的位置之间要么全被覆盖，要么全无，所以建树也可以用离散化后的坐标。

线段树能处理的信息要具有可合并性，现在有一个困难：线段树要维护每个位置具体被覆盖了几层（否则删边时不好处理），但每个被覆盖的位置最终都只会贡献 1。

遇到这种问题，我们就要想办法把它转化成可合并的信息。介绍一种简单的思路：我们可以用线段树维护当前区间内被覆盖的最小层数 s_1，再维护当前区间被覆盖 s_1 层的位置总长度 s_2，不难发现这两个信息都具有可合并性。这样在询问时，如果一段区间的 s_1=0，就返回区间长度减 s_2；否则返回区间的整段长度。

加入线段时，使用线段树维护 s_1,s_2 的操作是 O(\log n) 的，所以我们成功找到了例题 O(n \log n) 的解法。

算法实现：矩形面积并

首先是建线段树。这里维护的是区间，所以线段树的元线段（叶子结点）就可以取离散化后相邻的两个横坐标之间的区间。注意我们之前写线段树通常是维护序列上的数值，元线段取的是单个元素，可以视为点，所以此处以线段建立的线段树要相应地进行一些修改。

我采用的方法是：建树时用离散化后的下标，在 build 函数里处理好这段区间的真实长度和左右端点，之后的操作中就可以直接用原坐标了，更加方便。

:::info[建树的代码（行高亮部分是与序列建树不同的）]{open}

struct Segment_tree{
    int L,R,len;
    int s1,s2;
    int tag;
}s[N*8]; // 这里的 8 是 2n 条线段乘 4 倍的线段树
void build(int u,int l,int r){
    s[u].L=x[l],s[u].R=x[r]; // 此处线段树的叶子为一段线段而非一个点
    s[u].len=x[r]-x[l];
    if(r-l>1){
        int mid=(l+r)/2;
        build(u*2,l,mid),build(u*2+1,mid,r);//相邻的两个子区间
    }
    s[u].s2=s[u].len; // 最初覆盖层数全是 0
}

:::

:::info[线段树修改]{open}

不难发现区间在整体修改时其 s_2 是不变的，只有在下放再更新时才可能变化。

void update(int u,int l,int r,short p){
    if(l<=s[u].L&&s[u].R<=r){
        s[u].s1+=p;
        s[u].tag+=p;
    }
    else if(l<s[u].R&&s[u].L<r){ // 此处判断区间相交不能取等
        pushdown(u);
        update(u*2,l,r,p),update(u*2+1,l,r,p);
        pushup(u);
    }
}

:::

:::info[线段树查询]{open}

此处由于只会查询整个扫描线，就没必要专门写线段树的查询函数了。

if(s[1].s1==0) return s[1].len-s[1].s2;
else return s[1].len;

:::

pushup 和 pushdown 与普通线段树维护无异。接下来就是在主函数中按纵坐标遍历每条线段，当下一条线段的纵坐标不等于当前线段时，就说明一个时刻的扫描线更新完毕了，此时更新答案，即扫描线覆盖的长度乘上下一条线段与当前的纵坐标之差。

:::info[整体代码]

int n,x[N*2],tot;
struct line{
    int x1,x2,y;
    short p;
}a[N*2];
bool cmp(line a,line b){
    if(a.y!=b.y)return a.y<b.y;
    return a.p==1;
}
long long ans;
struct Segment_tree{
    int L,R,len;
    int s1,s2;
    int tag;
}s[N*8];
void pushup(int u){
    if(s[u*2].s1==s[u*2+1].s1){
        s[u].s1=s[u*2].s1;
        s[u].s2=s[u*2].s2+s[u*2+1].s2;
    }
    else if(s[u*2].s1<s[u*2+1].s1){
        s[u].s1=s[u*2].s1;
        s[u].s2=s[u*2].s2;
    }
    else{
        s[u].s1=s[u*2+1].s1;
        s[u].s2=s[u*2+1].s2;
    }
}
void build(int u,int l,int r){
    s[u].L=x[l],s[u].R=x[r]; // 此处线段树的叶子为一段线段而非一个点
    s[u].len=x[r]-x[l];
    if(r-l>1){
        int mid=(l+r)/2;
        build(u*2,l,mid),build(u*2+1,mid,r);
    }
    s[u].s2=s[u].len; // 最初覆盖层数全是 0
}
void pushdown(int u){
    if(s[u].tag){
        s[u*2].s1+=s[u].tag,s[u*2+1].s1+=s[u].tag;
        s[u*2].tag+=s[u].tag,s[u*2+1].tag+=s[u].tag;
        s[u].tag=0;
    }
}
void update(int u,int l,int r,short p){
    if(l<=s[u].L&&s[u].R<=r){
        s[u].s1+=p;
        s[u].tag+=p;
    }
    else if(l<s[u].R&&s[u].L<r){ // 此处判断区间相交不能取等
        pushdown(u);
        update(u*2,l,r,p),update(u*2+1,l,r,p);
        pushup(u);
    }
}
long long query(int u){ // 此处由于只会查询整个扫描线，就没必要专门写 query 函数了
    if(s[u].s1==0)return s[u].len-s[u].s2;
    return s[u].len;
}
int main(){
    cin>>n;
    for(int i=1,x1,x2,y1,y2;i<=n;i++){
        cin>>x1>>y1>>x2>>y2;
        x[++tot]=x1,x[++tot]=x2;
        a[i*2-1].x1=x1,a[i*2-1].x2=x2,a[i*2-1].y=y1,a[i*2-1].p=1;
        a[i*2].x1=x1,a[i*2].x2=x2,a[i*2].y=y2,a[i*2].p=-1;
    }
    sort(x+1,x+1+tot);
    tot=unique(x+1,x+1+tot)-x-1;
    build(1,1,tot);
    n*=2;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        update(1,a[i].x1,a[i].x2,a[i].p);
        if(a[i].y<a[i+1].y){
            ans+=query(1)*(a[i+1].y-a[i].y);
        }
    }
    cout<<ans;
    return 0;
}

:::

AC 记录。

常用技巧：点与矩形的相互转化

P1502：有 n 个点，每个点有坐标 x,y 和权值 l。求长宽为 W,H 的矩形能覆盖的点权之和最大值。Tn \le 10^5。

:::info[解法] 考虑矩形放在哪里时一个点会被覆盖住，若矩形的左下角在 [x_i-W+1,x_i] \sim [y_i-H+1,y_i] 这块矩形区域内，则第 i 个的 l_i 可以贡献上。

因此把 n 个点的可贡献范围整成矩形，看所有时刻的扫描线上单点最大值的 \max 即可。 :::

这个题告诉我们：在遇到点覆盖求区域的问题时，可以转化成矩形覆盖求单点的问题，从而更方便应用线段树等工具求解。

常用技巧：序列转二维正交

UVA1608：对于序列 a_1\sim a_n，如果对于所有 1\leqslant l\leqslant r\leqslant n，都有在连续子序列 a_l \sim a_r 中只出现 1 次的元素，则称这个序列是“不无聊的”。判断一些序列是否是“不无聊的”。

:::info[解法] 考虑每个位置上的元素能对哪些 [l,r] 产生贡献。记 a_i 在 i 之前最后出现的位置为 pre_i，在 i 之后首次出现的位置为 nxt_i，则在区间 [pre_i+1,nxt_i-1] 中，a_i 唯一出现。因此对于所有 pre_i<l\leqslant i 且 leqslant r<nxt_i，区间 [l,r] 一定都满足条件了。

序列 a_1\sim a_n 总共有 n^2 个连续子序列，我们可以将它们映射到平面直角坐标系上，一维代表 l，一维代表 r。则对于每个 a_i，它能确定的区间 [l,r] 正好构成一个矩形。因此我们扫描线计算所有 n 个矩形的面积并，如果最终的答案等于 n^2，说明所有的连续子序列都可以通过至少一个 a_i 满足唯一元素的条件，也就是整个序列满足要求。 :::

这个题告诉我们，有些看起来是序列问题的题目，可以通过“数形结合”思想的转化，用扫描线解决问题。

经典应用：二维数点

P10814：给定一个长度为 n 的序列 a，有 m 次询问，每次查询 a_l \sim a_r 之间小于等于 y 的元素个数。n,m,a_i \le 2\times 10^6。

将 a 中的每个元素放到平面直角坐标系上，横坐标为其下标，纵坐标为其大小。发现查询区间 [l,r] 中值在 [x,y] 之间的元素个数就等同于查询一个矩形覆盖了多少点。于是考虑将所有询问离线并拆成区间 [1,r] 的查询减去区间 [1,l-1] 的查询。然后就可以树状数组维护扫描线了。

求逆序对的数量就可以用二维数点解决，问题可以转化为从后往前遍历序列，对于每个 i，求区间 [i+1,n] 中，大小在 [0,a_i) 之间的数，再求和。而且这种求逆序对的方法可以在 O(n \log n) 的时间内对于一个序列的每个后缀，求出其逆序对数。