跳到主要内容

扫描线

引入​

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

二维矩形面积并问题​

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

过程​

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

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

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

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

笔记

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

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

实现​

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

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

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

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

需要 离散化。

练习​

B 维正交范围​

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

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

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

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

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

二维数点​

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

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

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

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

练习​

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

参考资料​

中等 (500)