扫描线

计算几何 / scanning

本地源文件：docs/geometry__scanning.md

扫描线

引入

扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题．

二维矩形面积并问题

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积．

过程

根据图片可知总面积可以直接暴力即可求出面积，如果数据大了怎么办？这时就需要讲到 扫描线 算法．

现在假设我们有一根线，从下往上开始扫描：

如图所示，把整个矩形分成如图各个颜色不同的小矩形，小矩形的高是扫过的距离，然而矩形的水平宽一直在变化．

给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1．每遇到一个水平边时，让这条边（在横轴投影区间）的权值加上这条边的标记．

Note

这个操作类似遍历括号序列：开括号加 1，闭括号减 1，「权值」对应当前位置的深度，「权值」是否大于 0，对应当前在不在括号里，也就是这段区间是否记入小矩形的宽度．

小矩形（不一定只有一个）的宽度就是整个数轴上权值大于 0 的区间总长度．

实现

用线段树维护矩形的长，也就是整个数轴上覆盖次数大于 0 的点．需求列举如下：

  • 一段区间权值加 1、减 1．
  • 统计整个数轴上，区间权值大于 0 的「区间长度和」．

如果你尝试直接用普通线段树模板来实现的话，也许会遇到些挫折．具体地，由于在区间加时，即使修改区间和节点管理区间重合，我们还是不能常数时间知道覆盖次数如何变化．这是因为我们不能直接知道：管理范围里有多长的区间会从 1 变成 0（从 0 变成 1）．

这道题只需要朴素的分治就能实现：维护每个节点管理区间中「完全覆盖区间的次数 v[]」（类似不用下放的懒惰标记）和「已覆盖的长度 w[]」两个信息．

需要 离散化．

洛谷 P5490【模板】扫描线 & 矩形面积并 参考代码

---|---

[「POJ 1151」Atlantis](http://poj.org/problem?id=1151) 参考代码

---|---

练习

  • 「POJ1177」Picture
  • 「POJ3832」Posters
  • [洛谷 P1856 [IOI1998] [USACO5.5] 矩形周长 Picture](https://www.luogu.com.cn/problem/P1856)
  • 横边贡献就是覆盖长度变化量．
  • 两个方向分别算一次可以避免竖直边的讨论．
  • 操作排序时注意考虑两个矩形边重合的情况．
  • 数据范围允许不用线段树，直接平方时间模拟．

B 维正交范围

B 维正交范围指在一个 B 维直角坐标系下，第 𝑖i 维坐标在一个整数范围 [𝑙𝑖,𝑟𝑖][li,ri] 间，内部的点集．

一般来说，一维正交范围简称区间，二维正交范围简称矩形，三维正交范围简称立方体（我们常说的二维数点就是二维正交范围）．

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

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

复杂度一般为 𝑂((𝑛 +𝑚)log⁡𝑛)O((n+m)log⁡n)．

二维数点

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

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

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

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

例题

[洛谷 P2163 [SHOI2007] 园丁的烦恼](https://www.luogu.com.cn/problem/P2163)

首先离散化．设一个左下角为 (0,0)(0,0)，右上角为 (𝑥,𝑦)(x,y) 的矩形内包含 𝑎𝑛𝑠𝑥,𝑦ansx,y 个点．则询问的答案答案可以被差分为 𝑎𝑛𝑠𝑐,𝑑 −𝑎𝑛𝑠𝑎−1,𝑑 −𝑎𝑛𝑠𝑐,𝑏−1 +𝑎𝑛𝑠𝑎−1,𝑏−1ansc,d−ansa−1,d−ansc,b−1+ansa−1,b−1．

代码

---|---

[洛谷 P1908 逆序对](https://www.luogu.com.cn/problem/P1908)

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

代码

---|---

[洛谷 P1972 [SDOI2009] HH 的项链](https://www.luogu.com.cn/problem/P1972)

简要题意：给定一个序列，多次询问区间 [𝑙,𝑟][l,r] 中有多少种不同的数．

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

在本题中，我们设序列中 𝑎𝑖ai 上一次出现的位置为 𝑝𝑟𝑒𝑖prei，如果 𝑎𝑖ai 没有出现过，则 𝑝𝑟𝑒𝑖 =0prei=0．根据题意，如果一种数在区间中出现多次，只会产生一次贡献．不妨认为每种数产生贡献的位置是区间中第一次出现的位置，这时可以发现，产生的总贡献即为 𝑝𝑟𝑒𝑥 ≤𝑙 −1prex≤l−1 的个数，反证法易证．

现在问题即为：给定一个序列 𝑝𝑟𝑒pre，多次查询区间 [𝑙,𝑟][l,r] 中有多少个 𝑝𝑟𝑒𝑖 ≤𝑙 −1prei≤l−1．

我们可以把 𝑝𝑟𝑒𝑖prei 看成二维平面的点：𝑖i 是横坐标，𝑝𝑟𝑒𝑖prei 是纵坐标，问题就转化为了二维数点问题：每次询问左下角为 (𝑙,0)(l,0)，右上角为 (𝑟,𝑙 −1)(r,l−1) 的矩形中有几个点．

注意到这个询问是可差分的，我们可以将询问差分为左下角为 (0,0)(0,0)，右上角为 (𝑟,𝑙 −1)(r,l−1) 的矩形减去左下角为 (0,0)(0,0)，右上角为 (𝑙 −1,𝑙 −1)(l−1,l−1) 的矩形有几个点，这样方便我们使用扫描线思想．

单次操作复杂度 𝑂(log⁡𝑛)O(log⁡n)，共有 𝑛n 次加点操作和 2𝑚2m 次查询操作，总时间复杂度 𝑂((𝑛 +𝑚)log⁡𝑛)O((n+m)log⁡n)．

代码

---|---

### 练习

  * [洛谷 P8593「KDOI-02」一个弹的投](https://www.luogu.com.cn/problem/P8593) 逆序对的应用．
  * [AcWing 4709. 三元组](https://www.acwing.com/problem/content/4712/) 上题的弱化版，同样为逆序对的应用．
  * [洛谷 P8773 [蓝桥杯 2022 省 A] 选数异或](https://www.luogu.com.cn/problem/P8773) HH 的项链魔改版．
  * [洛谷 P8844 [传智杯 #4 初赛] 小卡与落叶](https://www.luogu.com.cn/problem/P8844) 树上问题转序列问题然后进行二维数点．

总而言之，二维数点的主要思路就是数据结构维护一维，然后枚举另一维．

## 参考资料

  * [cnblogs/Yang1208：扫描线讲解，动态开点版线段树](https://www.cnblogs.com/yangsongyi/p/8378629.html)
  * [csdn/riba2534：POJ1151 Atlantis 题解](https://blog.csdn.net/riba2534/article/details/76851233)
  * [csdn/刀刀狗 0102：POJ1151 Atlantis 题解](https://blog.csdn.net/winddreams/article/details/38495093)
  * [浅谈扫描线](https://www.luogu.com.cn/article/f8q5bmnz)

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/geometry/scanning.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/geometry/scanning.md "edit.link.title")
>  __本页面贡献者：[H-J-Granger](https://github.com/H-J-Granger), [Ir1d](https://github.com/Ir1d), [Enter-tainer](https://github.com/Enter-tainer), [sshwy](https://github.com/sshwy), [StudyingFather](https://github.com/StudyingFather), [Catreap](https://github.com/Catreap), [countercurrent-time](https://github.com/countercurrent-time), [NachtgeistW](https://github.com/NachtgeistW), [Tiphereth-A](https://github.com/Tiphereth-A), [AngelKitty](https://github.com/AngelKitty), [CCXXXI](https://github.com/CCXXXI), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [Dregen-Yor](https://github.com/Dregen-Yor), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [scp020](https://github.com/scp020), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [abc1763613206](https://github.com/abc1763613206), [c-forrest](https://github.com/c-forrest), [Gary-0925](https://github.com/Gary-0925), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [Great-designer](https://github.com/Great-designer), [HeRaNO](https://github.com/HeRaNO), [iamtwz](https://github.com/iamtwz), [jpy-cpp](https://github.com/jpy-cpp), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [mcendu](https://github.com/mcendu), [mxr612](mailto:m_gt_@outlook.com), [Peanut-Tang](https://github.com/Peanut-Tang), [ShelpAm](https://github.com/ShelpAm), [shuzhouliu](https://github.com/shuzhouliu), [SukkaW](https://github.com/SukkaW), [Xeonacid](https://github.com/Xeonacid), [xiao-ming-hub](https://github.com/xiao-ming-hub)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用