#创作计划# 扫描线
2025-11-03 21:59:03
发布于：广东
水一篇创作计划加精。
由于学业原因，本文将逐步更新。
前言
建议读者在阅读本章内容之前，先掌握树状数组与线段树的有关内容。
当然，还没掌握这些内容并不影响你点赞
算法介绍
扫描线算法，顾名思义，就是用一条线扫过一个二维的平面，将问题简单化为一维问题。
然后可以通过线段树进行维护，达到省时的效果。
当然，如果你没看懂上面这段话，请接着往下看，我们将通过一些例子一起理解扫描线算法。
算法引入
让我们先来看一道线段树的经典问题。
有一个长度为 的数组，初始元素均为 0，给你三种操作：
- 在某个位置进行 +1 操作；
- 在某个位置进行 -1 操作；
- 求区间和。
这不就是一道经典的单点操作，区间查询的题目吗？甚至能用树状数组维护。
那么我们再来看一道题。
给定一个 个数的数组， 次询问：
每一次查询某个区间中不同元素的个数。
是不是突然感觉有点不知所措了？
分析
每次都要查询一个区间中不同元素的个数，那么我们能不能想一种办法，让每一次查询时能快速算出答案呢？
让我们来看一下。
假设这里有一个 11 个数的数列，元素的大小如下图。
接着，我们用一条线扫过这个数组，会依次得到下面这些画面，看仔细了。
第一位：
将扫过的 1 做上标记，因为它是第一次出现。
第二位：
扫过 5，第一次出现，做上标记。
第三位：
扫过 2，第一次出现，做上标记。
第四位：
这位很关键，我们发现扫到了一个重复的 2，之前已经出现过了。
我们该怎么办？
我们将原本的 2 的标志擦掉，并给后面的 2 加上一个标记。
第五、六位：
紧接着下面两位都打上标记。
第七位：
发现重复的 5，将原本的 5 擦掉，给新的 5 打上标记。
假设我们先扫描到这里。
那我们如何求最终答案呢？
假设给的区间是 ，那么显而易见答案是 4，和标志有什么关联呢？
是的，我们发现这段区间当中有 4 个未被抹掉的标志，所以答案就是 4。
区间中有几个未被抹掉的标志，说明有几个不重复的数，所以答案就是几。
总结做法
将打标记转换为在此位置 +1，去除标记表示在这个位置 -1，那么求标记个数其实就是求区间和。
所以，问题转换为：
有一个长度为 的数组，初始元素均为 0，给你三种操作：
- 在某个位置进行 +1 操作；
- 在某个位置进行 -1 操作；
- 求区间和。
咦？怎么感觉这个问题有点眼熟？往上划你就会发现这就是刚刚的那道最基础的线段树/树状数组问题。
至此，我们解决了这道题，其实这就是扫描线。
提炼思路
还记不记得在文章的最开始所说的扫描线的定义？
- 扫描线算法，顾名思义，就是用一条线扫过一个二维的平面，将问题简单化为一维问题。
可是这个问题中哪有二维呢？
其实，这个问题可以翻译为：对于第 个元素 ，把他看作平面上的一个坐标点 。
询问等价于 坐标在一个 坐标区间内的区域中有多少行有点。
经典例题
未完成。
有帮助，赞一个