扫描线

引入

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

Atlantis 问题

题意

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

解法

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

过程

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

• 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
• 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1，每遇到一个矩形时，我们知道了标记为 1 的边，我们就加进来这一条矩形的长，等到扫描到 -1 时，证明这一条边需要删除，就删去，利用 1 和 -1 可以轻松的到这种状态。
• 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 和 。
• 需要
  离散化。

实现

练习

• 「POJ1151」Atlantis

• 「POJ1177」Picture

• 「POJ3832」Posters

• 洛谷 P1856[IOI1998][USACO5.5]矩形周长 Picture

B 维正交范围

B 维正交范围指在一个 B 维直角坐标系下，第 维坐标在一个整数范围 间，内部的点集。

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

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

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

复杂度一般为 。

二维数点

给一个长为 的序列，有 次查询，每次查区间 中值在 内的元素个数。

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

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

先将所有的询问离散化，用树状数组维护权值，对于每次询问的 和 ，我们在枚举到 时统计当前位于区间 内的数的数量 ，继续向后枚举，枚举到 时统计当前位于区间 内的数的数量 ， 即为该次询问的答案。

可以用 洛谷 P2163[SHOI2007]园丁的烦恼 这道题进行练习。

例题

例题

• 洛谷 P8593「KDOI-02」一个弹的投 逆序对的应用。

• AcWing 4709. 三元组 上题的弱化版，同样为逆序对的应用。

• 洛谷 P8773[蓝桥杯 2022 省 A]选数异或 HH 的项链魔改版。

• 洛谷 P8844[传智杯 #4 初赛]小卡与落叶 树上问题转序列问题然后进行二维数点。

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

参考资料

• https://www.cnblogs.com/yangsongyi/p/8378629.html

• https://blog.csdn.net/riba2534/article/details/76851233

• https://blog.csdn.net/winddreams/article/details/38495093

• https://dregen-yor.cf/2022/10/01/sao-miao-xian