扫描线 • CoderXL's Blog

头图来自 OI-wiki ↗，展示的是从下向上扫描，而我的实现是从左到右扫描。

问题#

求矩形面积并。

思路#

类似微积分/割补法，在一个维度上扫描，在另一个维度上维护“穿过的线的总长度”，然后对扫描的间隔 $\times$ 长度求和。

实现#

大致规划#

如何维护扫描线穿过矩形的长度呢？

我们考虑：在扫描线延伸的方向维护一个支持区间修改、查询的数据结构，然后每次扫描线移动到矩形的边上时，要么是进入该矩形，要么是离开：进入时，给该边覆盖的范围内的区间数值统一 $+1$ ；离开时则 $-1$ . 而每次需要查询全局内数值大于 $0$ 的位置有多少个。

细节#

线段树#

这个“支持区间修改、查询的数据结构”显然就要使用线段树了。但这个线段树比较特殊，为了理解这个线段树和一般线段树的区别，我们列一个列表：

	普通线段树	扫描线的线段树
区间修改	✅（加减法区间任意）	✅（同一个区间，经历过一次加法就必定会经历一次减法）
区间查询	✅（任意区间）	✅（只有全局查询）
统计指标	区间和、最大值等等	全局非零位置个数

可以看到，我们要维护“区间内有多少位置非零”，记作 s[rt]，其中 rt 是某个区间节点。

但是，仅仅维护这个 s 是不够的，因为你无法知道区间减法的时候，“非零位置个数”应该减少多少。

举个例子：

初始时原序列 0 0 0
给前两个位置 $+1$ ，原序列变为 1 1 0，“非零位置个数”为 $2$
给后两个位置 $+1$ ，原序列变为 1 2 1，“非零位置个数”为 $3$
给后两个位置 $-1$ ，原序列变为 1 1 0，但是由于只维护了 s，无法得知此时应该变为 $1$ 还是 $2$ ，甚至是维持 $3$ 不变。

因此，除了 s 之外，还需要额外维护一点什么。

一个想法是维护每个位置的数值，但这个量只有在叶子节点的时候有意义，没法扩展到区间上来快速获得“非零位置个数”的相关信息。

你也许会说：我可以在每次区间减法的时候，继续递归到叶子节点啊。

但是，线段树的时间复杂度的正确性就来源于：当对一个区间节点整体操作时，不需要借助递归到下层来完成。只有这样，对于任何长度为 $n$ 前缀区间，它都至多要被分成 $O(\log n)$ 个区间就能被线段树处理完。而对于任何一般区间，都会在某一层跨过某条区间中线从而变成一个前缀和一个后缀区间，因此复杂度也是 $O(\log n)$ 的。但是，如果每个区间操作都需要拆分到叶子节点，那么复杂度就是 $O(n\log n)$ 的了。

那么这个线段树到底该维护什么呢？

我们只需要维护“当前区间被完整覆盖的次数” v[rt].

这个信息能帮助我们什么？它可以让我们在 v[rt]>1 的时候，直接得知整个区间减法的结果：s[rt] 不变，v[rt]--. 但是一旦 v[rt] 减到 $0$ ，那么我们就不知道这时候 s[rt] 应该变成什么了，之前的问题仍然部分存在。

但是，由于我们只关心全局查询，每次减法操作的区间也严格等于先前某次加法操作的区间，因此我们惊讶地发现，我们不需要做 push_down. 这就意味着，父区间的信息更新不会覆盖子区间，而当父区间的 v[rt] 减小到 $0$ 之后，它可以直接令 s[rt]=s[ls]+s[rs]. 因为所有完整覆盖了 rt 区间的操作，都没有影响到 ls 和 rs，现在这些操作被撤回了，ls 和 rs 那里还保持着子区间的精细状态。

离散化#

但是扫描线的坐标范围一般较大，需要离散化。离散化之后，线段树的每个叶子不再代表一个坐标，而是代表一条线段。而区间修改就表示这条线段被加入了/删除了，区间查询就是非零位置对应线段的长度求和。注意坐标离散化之后数量为 nn，但是这些坐标组成的线段数量是 nn-1，因此线段树大小应为 nn-1.

此外，注意离散化之后，g 数组从 $0$ 开始，但是为了适应线段树，点的坐标从 $1$ 开始。每个点对应以其为左（下）端点的一个线段，坐标为 $i$ 的点对应的线段的长度是 g[i]-g[i-1]

代码#

P5490 【模板】扫描线 & 矩形面积并 ↗

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 100010, NN = N<<3;

int n,nn;
ll ans;

int g[N<<1];

struct Line
{
    int x;
    int l,h;
    bool in;
    bool operator<(const Line&b)const
    {return x<b.x;}
}line[N<<1];

struct Sgt
{
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((tl+tr)>>1)
    int v[NN],s[NN];
    void pushp(int rt,int tl,int tr)
    {
        if(v[rt])s[rt]=g[tr]-g[tl-1];
        else if(tl>=tr)s[rt]=0;
        else s[rt]=s[ls]+s[rs];
    }
    void build(int rt=1,int tl=1,int tr=nn-1)
    {
        if(tl>=tr)v[rt]=s[rt]=0;
        else
        {
            build(ls,tl,mid);
            build(rs,mid+1,tr);
            pushp(rt,tl,tr);
        }
    }
    void add(int rt,int tl,int tr,const int&l,const int&r,const int&x=1)
    {
        if(r<tl||tr<l)return;
        if(l<=tl&&tr<=r)
        {
            v[rt]+=x;
            pushp(rt,tl,tr);
            return;
        }
        add(ls,tl,mid,l,r,x);
        add(rs,mid+1,tr,l,r,x);
        pushp(rt,tl,tr);
    }
    void add(const int&l,const int&r){add(1,1,nn-1,l,r,1);}
    void del(const int&l,const int&r){add(1,1,nn-1,l,r,-1);}
    ll query(){return s[1];}
#undef ls
#undef rs
#undef mid
}sgt;

signed main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        line[i<<1]={x1,y1,y2,true};
        line[i<<1|1]={x2,y1,y2,false};
        g[i<<1]=y1;
        g[i<<1|1]=y2;
    }
    sort(g,g+(n<<1));
    nn=unique(g,g+(n<<1))-g;
    if(nn<2)
    {
        cout<<0;
        return 0;
    }
    for(int i=0;i<n;i++)
    {
        int l=line[i<<1].l;
        int h=line[i<<1].h;
        l=lower_bound(g,g+nn,l)-g+1;
        h=lower_bound(g,g+nn,h)-g+1;
        line[i<<1].l=line[i<<1|1].l=l;
        line[i<<1].h=line[i<<1|1].h=h;
    }
    sort(line,line+(n<<1));
    sgt.build();
    for(int i=0,_x=0;i<n<<1;i++)
    {
        ans+=(line[i].x-_x)*sgt.query();
        _x=line[i].x;
        if(line[i].in)sgt.add(line[i].l,line[i].h-1);
        else sgt.del(line[i].l,line[i].h-1);
    }
    cout<<ans;
    return 0;
}

cpp