Preface
本文部分题目摘自 lxl 的数据结构系列课件
由于工程量巨大，难免会出现错字、漏字的情况，如果影响到了您的阅读体验，还请私信我，我会在第一时间修复。
本文建议大家有一定的数据结构基础后再来阅读 /heart。
个人感觉扫描线不是难点，难点在于怎么抽象模型。
首先需要明白一个东西，叫做
由于出题人直接把坐标系怼在我们脸上了，只需要考虑扫描线的部分就好了。
把矩形拆成入边和出边，然后在
转化一下题意先：
考虑套用上面写的套路，将每个区间表示为二维平面上的点 \((l',r')\)。
首先初始化 \((l',r')\) 的权值为 \(r' - l'\)，显然，对 \(l \in [1,n]\) 做矩形减，对 \(r\in [1,n]\) 做矩形加。
呆一点的，在序列上进行最值分治（你用单调栈也行），具体地说，每次分治的序列中的最大/最小值都是分支中心，然后 \(\max\) 进行矩形加，\(\min\) 进行矩形减。
此时，问题被转化为给定一个平面，进行 \(O(n)\) 次矩形加减，问一个矩形内部有多少 \(0\)。根据前面的推论，显然询问矩形是一个 2-side 矩形。然后使用扫描线和线段树沿着横/纵轴扫描整个平面，并把前面的矩形加减拆成线上序列加减（这个算平凡的）。
由于矩形内元素一定非负，所以套用「矩形面积并」时的线段树维护套路，即可计算 \(0\) 的个数。
问题来了，我们在扫描线后的 2-side 矩形询问，需要查询一个区间在前缀时间中 \(0\) 的个数，这个线段树打个历史标记也可以做，不过需要细细的讨论一下，注意细节。
时间复杂度 \(O((n+m)\log n)\)。
EC final 2020 G. Prof. Pang's sequence
问题转化：
依旧是考虑将区间转化为平面上的点，建系，让横轴为序列维（对应询问 \(r\)），纵轴也为序列维（对应询问 \(l\)），扫描线在横轴上跑。
考虑扫描的过程中遇到一个值 \(a_r\)，考虑找到 \(a_r\) 的前驱 \(a_p\)，则对于左端点在 \([p+1, r]\) 的所有区间来说，\(a_r\) 是一种新的颜色，否则不应发生变化。
现在问题就简单了，由于我们线上的每个位置只会是 \(0/1\) 的取值，所以我们在扫描线上维护一个「区间取反，区间和」这样的一个东西，查询就变成每依次区间查询，然后贡献给对应的查询矩形。
不过这样查询显然是要死掉的，所以差分一下，就变成了查询区间历史和，仿照上一个题用线段树简单维护即可。
时间复杂度 \(O((n+q)\log n)\)。
P8421 [THUPC2022 决赛] rsraogps / P9335 [Ynoi2001] 雪に咲く花
全新的视角。
离线做扫描线，将询问变成矩形，由于询问信息可差分，直接在每个位置 \(i\) 上维护询问信息的前缀和 \(s_i\)，询问答案减一下就好了。
现在考虑怎么维护这个前缀和，考虑扫描线向右移动 \(1\)，如果这个时候 \(A_i,B_i,C_i\) 均未发生变化，那么 \(s_i\) 的变化量肯定与上次移动保持一致，于是不难想到将 \(s_i\) 变成一个一次函数的形式 \(k_ix+b_i\)，现在要修改的就只剩下 \(A_i,B_i,C_i\) 发生变化的部分，不难发现 \(A_i,B_i,C_i\) 只会发生 \(O(\log V)\) 次变化，总共发生 \(O(n\log V)\) 次变化，所以直接暴力修改就好。
时间复杂度 \(O(n \log V + m)\)。
可供练习的题：
对一维分治
有些时候，我们所维护的信息不能差分，这个时候就需要祭出我们的分治。
考虑对一维度分治后，此时将一个 4-side 矩形变成两个 3-side 矩形（考虑从中间劈开，然后变成两个开口相对的 3-side 矩形），跑两边扫描线，就可以做到只有插入没有删除了。
由于分治每一次处理所有跨过分支中心的矩形，然后在向下继续分治，所以复杂度会多一个 \(\log\)，复杂度证明请类比归并排序。
P1609 [Ynoi2009] rprmq1
由于这个题实在是太毒瘤了，这里就不放题解了，大家自己做做就好 /dk
二维扫描线
我们发现，一维扫描线是对某个维度排序，每次查询 \([1,l]\) 的信息，然后沿着从 \(1\) 到 \(n\) 的路径扫描全部的询问。
那啥是二维扫描线呢？套用一维扫描线的行为，我们尝试得到二维扫描线的行为：
实际上就是莫队，这个可以看看 Alex_Wei 的莫队学习笔记，这里不多赘述。
自由度
考虑一维扫描线 \(+\) 一维数据结构可以处理二维静态问题。
然而实际上普通的维护序列问题实际上也属于两个维度。
因为是按照给定的操作序列操作的，这里不乏出现时间的维度。
所以每一次操作都可以看做是一个 3-side 矩形，然后时间一维，序列一维，在时间维上做扫描线，就将二维静态问题转化为了一维动态问题。
于是这启发我们：
扫描线序列维，数据结构时间维
由于序列上的动态操作可以看做成是序列一维，时间一维。
所以在有些情况下我们直接沿着时间维度跑不好处理，这个时候我们就可以考虑在序列维度上做扫描线，然后线上维护时间维。
这种问题一般都是在线上查询一个单点的信息，当然，形势好的话查询区间信息也是可以的。
Comet OJ - Contest #14 D / P8512 [Ynoi Easy Round 2021] TEST_152
直观的看这个题似乎特别不好处理。
不妨从贡献的角度看这个题，把「经过操作序列上 \([x,y]\) 的操作后形成的最终序列上每个位置的和」给拆成「每个时间点对最终序列的贡献的和」。
这会产生两个性质：
- 某个时间产生的贡献会随着时间的流逝逐渐消失，换句话说，时间点 \(i\) 产生的贡献是不增的。
- 时间点 \(i\) 的贡献是无后效性的，他不会受到前面的时间的影响，他只会被后面的时间所影响，这样就意味着执行了 \([1,y]\) 操作和执行了 \([x,y]\) 操作后，时间点 \(x\) 的贡献一致。
现在容易想到建系，横轴为操作序列维，纵轴为时间维，然后辅助维护一个执行完 \([1,y]\) 操作的 \(c\) 数组。
考虑扫描线在横轴上跑，线上维护每个时间点对当前 \(c\) 数组的贡献，然后查询就是线上的一个区间和。
现在考虑扫描线右移会发生什么，假使遇到了操作 \((l',r',v')\)，则此时对 \(c\) 数组进行操作就是 \(c_i\gets v'\quad(i\in [l',r'])\)，在增量的视角中就是 \(c_i\) 增加了 \(v'-c_i\)，然后在线上减少那部分时间点的贡献，最后增加当前时间点的贡献。显然，线上一个树状数组就够了。
由于在我们给 \(c\) 数组赋值的时候是一个颜色段均摊，所以时间复杂度还是 \(O((n+m)\log n)\)。
P5524 [Ynoi2012] NOIP2015 充满了希望
感觉正着扫做操作 \(1\)、\(2\) 可能是个天坑，于是考虑倒着做扫描线，也就是固定左端点，自由右端点。
考虑一个操作 \(3\) 在前面被一个操作 \(2\) 覆盖了，则左边面的所有操作对当前操作来说都无效了，也就是每个操作 \(3\) 只会被覆盖一次。
再考虑操作 \(1\) 对操作 \(3\) 的影响，发现如果操作 \(3\) 已经被操作 \(2\) 覆盖了，则此时的操作 \(1\) 是无用的；如果没被覆盖，则说明在未来我们的 \(x,y\) 的意义是反着的，此时若有操作 \(2\) 覆盖了 \(y\) 等于在操作 \(1\) 后面覆盖了 \(x\)，这一个性质启发了我们遇到操作 \(1\) 时应该直接交换，这样才不影响正确性。
然后站在操作 \(2\) 的角度上观察，发现有可能一次操作 \(2\) 会在同一个位置覆盖掉多个操作 \(3\)，这启发我们用 vector 维护每个位置的操作 \(3\)。
更加深入的，发现交换操作等价于「两次单点染色」，发现待覆盖的区域和一次覆盖的区域可以颜色端均摊，用 ODT 维护这个颜色端均摊就好。
综上，不难得出扫描线左移是我们需要干什么：
- 遇到操作 \(1\) 时：直接交换两个位置的
vector，ODT 上交换两个位置的颜色。 - 遇到操作 \(2\) 时：ODT 上区间染色 \(1\)，然后对每一个颜色为 \(0\) 的位置依次处理完询问，并清空
vector。 - 遇到操作 \(3\) 时：ODT 单点染色 \(0\)，然后将当前操作编号压入对应位置的
vector中。
每次查询的时候就是一个区间和，直接树状数组维护就好，时间复杂度 \(O((m+q)\log n)\)。
P7560 [JOISC 2021 Day1] フードコート
建系，横轴为序列维，纵轴为时间维，扫描线在横轴上跑。
此时操作序列中的修改变成了横着的线，询问变成了竖着的线，横向差分一下，就变成了「单点修改、区间查询」。
思考如何做查询（也就是做操作 \(3\)），假设我们是在 \(i\) 时刻做的操作 \(3\)，那么只需要找到 \(i\) 之前最近一次队列空的时候 \(t\)，在时间 \([t, i]\) 之间的每一次 pop 必然都是有效的，否则的话中间必然还要再空一次，不满足「最近」这一个条件，这样查询操作就变成了在这一个区间里面二分了。
考虑如何刻画这个最近一次队列空，设 push \(t\) 个元素为单点 \(+t\)，pop \(t\) 个元素为单点 \(-t\)，此时距离 \(i\) 时刻最近一次队列空的时刻就是 \([1,i]\) 中最靠右的最大后缀和的位置，证明如下：
由于会出现单点 \(-t\) 这种牛魔东西不好二分，所以不如直接维护后缀和，这时候单点 \(\pm t\) 变成前缀 \(\pm t\)，然后查询的时候注意别忘记消减掉后面时间带来的影响。如果此时我们查出来的 \(\lt k\)，那么可以直接跑路了，因为此时队列必定没有 \(k\) 个元素。
现在我们已经找到了最近一次队列空的时间 \(t\)，思考如何在 \([t,i]\) 上二分，首先查出 \([t,i]\) 中的 pop 量，然后给这个 pop 量加上 \(k\)，表示要找第 \(k\) 个位置，在 \([t,i]\) 上找到第一次 \(\ge\) pop 量的位置，然后读取这个位置的属性，即为答案，时间复杂度 \(O((n + q)\log n)\)。
别忘了还原消减操作！！！
P8518 [IOI2021] 分糖果
建系，横轴为序列维，纵轴为时间维，套用 P7560 的套路，只要我们找到了最后一次触碰上界或者下界的时刻 \(t\)，在 \(t\) 时刻之后的部分就变成了一个简单的求和，或者找到一个刻画 \(t\) 时刻之后部分贡献的方法。
那么目前亟待解决的问题就是如何描述「最后一次触碰上/下界」这一个东西。
设当前正在被操作的原序列 \(A\) 位置为 \(j\)，时间序列为 \(time\)，定义「制裁」为「当前操作结束后触碰到上/下界时，对\(a_j\) 取 \(\min\) 或 \(\max\) 」的行为，定义「触碰」为「当前操作结束后，位置 \(a_j \gt c_j\) 或 \(a_j \lt 0\)」。
先忽略上界，考虑什么时候会碰到下界，不难发现在时间序列的最小前缀和 \([1,x]\) 中的 \(x\) 上，证明如下：
现在考虑加上上界，不难发现下面这个性质：
- 若 \(i\) 时刻触碰上界，\(j\) 时刻触碰下界，则时间序列上 \([i,j]\) 区间的和一定 \(\lt -c\)。
- 若 \(i\) 时刻触碰下界，\(j\) 时刻触碰上界，则时间序列上 \([i,j]\) 区间的和一定 \(\gt c\)。
综上，得「相邻的上下界触碰事件」之间区间的和的绝对值一定 \(\gt c\)。
现在我们的「最后一次触碰上/下界」一定在最靠左满足这一条件的区间的左端点或者右端点，然而左端点只会有一种情况（就是有可能在触碰下界后一段或触碰上界后一段的区间和的绝对值 \(\gt c\)），对于这种情况我们取一下当前序列的前缀最大/小值就好了。
最后就剩怎么找我们所需要的那个区间，简单的，考虑线段树维护「前缀最小和、前缀最大和、区间和」，然后绝对值最大子段和就是「前缀最大和 \(-\) 前缀最小和」，修改是单点修改，查询时在线段树上二分即可。
时间复杂度 \(O((n+q)\log q)\)。
UOJ 515. 【UR #19】前进四
你会发现这个东西长得很像我们的楼房重建，那么自然不难想到两个 \(\log\) 的做法，不过这里的期望时间复杂度为单 \(\log\)。
考虑离线，建系，设横轴为序列维，纵轴为时间维，考虑倒着在序列维上做扫描线，线上维护时间。
转换角度观察这个问题，发现每一次单点修改都影响了从「本次修改」到「下一次修改」的整个时间，故在线上维护取 \(\min\) 修改，然后发现查询等价于查询截止到这个时间，一共发生了多少次成功的取 \(\min\) 操作，换句话说，就是截止到当前时间、当前位置的后缀最小值一共变了几次。
上面这一车东西考虑做「Segment tree beats」，时间复杂度 \(O((n+Q)\log n)\)。
计算几何中的扫描线
回归扫描线的本质，实际上就是拿一条线去扫平面来获得所需要的信息。
因此较为显然的，我们也可以将扫描线用在计算几何中。
通常的套路是维护扫描线与几何图形截点的位置，与几何图形下一个拐点的位置。
由于我的计算几何很菜，所以只能说两个比较简单的题目。
交点检测
扫描线扫描 \(x\) 轴，线上维护纵轴，也就是每个线段与扫描线的交点。
这样有了一个较好的性质，就是如果线段 \(l\) 要与其他线段产生交点，必定先与在扫描线上的相邻线段有交点。
那么此时维护扫描线上相邻线段什么时候发生交点，计算交点并在扫描线上交换两个线段的位置。
由于是线段，所以还需要维护线段的加入事件和删除事件。
综上，用平衡树维护一下上述操作就好了，设交点数为 \(o\)，则时间复杂度为 \(O((n + o)\log n)\)。
平面图点定位
类比交点检测，发现如果出现了交点，则说明这个的一个区域被封闭了。
这样一直做就可以找到所有区域以及相邻区域。
设区域数为 \(o\)，则时间复杂度为 \(O((n + o)\log n)\)。
可供练习的题：
树上扫描线
考虑在序列上的时候我们的询问会转化为 \(O(1)\) 个矩形。
现在问题上树，不难想到将树上问题转化为序列上的问题，故进行树链剖分。
这里利用了一个树链剖分的一个非常优秀的性质：「树上的任意一条路径划分成不超过 \(O(\log n)\) 条连续的链」。
由于这一个性质，我们将拆分出来的链分别做矩形，此时最多会出现 \(O(\log n)\) 个矩形。
如果考虑路径上点之间的关系的话，则最多会出现 \(O(\log^2 n)\)。
然后我们就在原先复杂度基础上多了一个或者两个 \(\log\)，复杂度在大部分情况下依旧是可以接受的。
未知渠道获取的题
考虑整除分块，预处理出所有符合条件的点对。
建系，设横纵坐标都为序列维（dfn 维），则点对变成平面上的点。
对于每个路径，预处理所有可能的询问矩形，即两个链组合在一起组成一个询问矩形，由于树链剖分的性质，不难发现矩形数是 \(O(q\log^2 n)\) 的。
然后现在的问题就变成一个简单的二维数点，时间复杂度 \(O(q \log ^ 3 n + n \sqrt m \log n)\)，足以通过该题，由于常数极小，把标算给锤了。
可供练习的题：