浅谈扫描线

· · 算法·理论

可能更好的阅读体验：隙间传送

Preface

本文部分题目摘自 lxl 的数据结构系列课件

由于工程量巨大，难免会出现错字、漏字的情况，如果影响到了您的阅读体验，还请私信我，我会在第一时间修复。

考虑到一些题目不易访问，所以在部分题目下面给出了简要题意，其余未给出简要题意的题目均给出了题目链接 qwq。

本文建议大家有一定的数据结构基础后再来阅读 /heart。

个人感觉扫描线不是难点，难点在于怎么抽象模型。

首先需要明白一个东西，叫做 B 维正交范围

在一个 B 维直角坐标系下，第 i 维的坐标在范围 [l_i, r_i] 之内，则符合这些限制的点构成的的点集为 B 维正交范围。

当每个维度都是两个端点的限制时，我们管它叫 2B-side 的 B 维正交范围。

如果部分维度只有一个端点的限制，我们管它叫 A-side 的 B 维正交范围。

如果有维度没有限制，则显然，这个维度不参与构成正交范围。

一维扫描线

当处于一个静态的二维平面上时，我们不难想到用扫描线来扫描其中的一个维度，用数据结构来维护另一个维度。

在扫描线扫描的过程中（例如从左到右扫），可能会在数据结构上产生一些修改和询问。

如果信息可差分，则直接差分，否则需要分治。

如果从序列的角度上来看的话，不难发现扫描线做的实际上是枚举询问右端点，维护左端点答案。

假设当前的信息是一个 4-side 的信息，这个时候如果信息满足差分，就可以把 4-side 矩形差分成 3-side，然后这个时候就可以直接做一维扫描线，我们让扫描线扫描一个 side，剩下所需要维护的信息就是一个 2-side 的信息，说人话就是一个区间操作的信息。

静态区间查询类问题

静态的序列，只有区间查询。

一般维度只有 2。

二维数点

给定一个长为 n 的序列，有 q 次询问，每次问你区间 [l, r] 中有多少位置上的数在范围 [x,y] 之内。

首先，不难发现所查询的是一个 4-side 矩形内部的点的个数，这类问题一般叫做「二维数点」，是一类很经典的问题。

首先考虑一下怎么建系，由于题目直接把坐标系怼你脸上了，所以不难看出可以让一个轴表示值域维，另一个轴表示序列维，然后显然，序列维上是容易差分的，所以在序列维上差分，将范围从 4-side 降到 3-side，这个时候就好办了，扫描线扫描序列维剩下的那一个 side，然后在扫描线上就变成了查询 [x,y] 上点的个数，不难想到用树状数组解决，时间复杂度 O((n+q) \log n)。

基础问题

给定 n 个矩形，然后有 m 次询问，每次询问给定一个点，问这个点被多少矩形所包含。

范围懒得给了，反正要求单 \log。

如果站在询问的点的角度来看，似乎问题不是很好解决。

不妨这次来试着拆一下贡献，看看每个矩形都贡献了什么，不难发现每个矩形都将这个矩形内的点被套的次数 +1。

这样就爽了，考虑直接建系，横轴就是题目中的 x 轴，纵轴就是题目中的 y 轴，然后依旧是熟悉的配方，将 4-side 的矩形给差分成 3-side 的矩形，也就是将每个矩形拆成入边和出边。现在用扫描线扫描 x 轴（当然，扫描 y 轴也可以），在线上维护一个 2-side 的区间，当扫描到入边的时候，意味着区间 +1，扫描到出边的时候，意味着区间 -1，然后每个查询的点对应到线上就是单点查询。

时间复杂度 O((n+q)\log n)。

P1972 [SDOI2009] HH 的项链

老典题了。

不妨先尝试建系，让一个轴为序列维，让一个轴为值域维，然后你会发现这个不同的数的个数似乎特别不好维护。

不妨让点都具有超能力，当扫描线扫描到和他相同的值时，把前驱的贡献转移到当前位置（可以认为点直接瞬移到扫描线所在的位置上），这样的转化就不难将原问题变成一个 2-side 的区间了，考虑维护一个 now 数组，表示当前这个点所在的位置。然后扫描序列维（对应询问 r），在线上也维护序列维（对应询问 l），表示当前位置贡献了多少点，则不难发现这是一个「单点加/减」和「区间查」的需求，用树状数组维护即可，最后考虑每次向右扫描的时候，更新 now 数组和线上的树状数组，此时时间复杂度为 O((n+q)\log n)。

BZOJ 3489 A simple RMQ problem（弱化版）

给定长为 n 的序列，m 次查询区间中有多少值只出现一次。

要求单 \log。

你不难发现当一个区间内出现两个相同的数时，这个数就不产生贡献了。

于是类比上面的「HH 的项链」，我们不难想到当我们扫描线扫到一个数时，让其贡献为 +1，让其前驱的贡献为 -1，让其前驱的前驱的贡献为 0，然后剩下的就和「HH 的项链」一样了。

CF522D Closest Equals

考虑直接建系，设横轴为序列维（对应询问 r），纵轴也为序列维（对应询问 l），然后我们在横轴上做扫描线。

现在考虑扫到一个数要做什么，首先，显然的是，至少要有一对数才有「距离」这个概念，然后我们在扫描的时候都是在扩张询问的右端点，所以不妨让相邻两个点中靠左的那个点的位置维护距离，这样就变成了在线上维护「单点修改，区间查询最小值」了。

时间复杂度 O((n+m)\log n)。

P4137 Rmq Problem / mex

考虑建系，设横轴为序列维，纵轴为值域维，在序列维上做扫描线，线上维护最小值，然后扫描线的移动就是线上的单点修改，查询就是在扫描线上进行二分，这里用线段树维护线上的信息即可。

时间复杂度 O((n+m)\log n)。

未知渠道获得的题

给定一棵 n 个点的树，然后有 q 次查询，每次查询区间 [l,r]，表示询问当这个树仅剩点和边的编号在 [l,r] 之间时连通块的个数。

要求单 \log。

考虑这里的连通块个数等于啥，显然等于「点数 - 边数」，然后点的个数是简单的（恒定 r - l + 1），因为范围内的点肯定会被算入到贡献之中。

但是边不一定，因为有可能它连接了超出 [l, r] 范围的点，这样的边是不能被计算进去的，所以现在我们要做的处理「边数」这一部分的贡献。不妨先冷静下来，考虑影响一个边是否是有效边的因素有哪些，不难想到是「边的两个端点是否属于 [l,r]」和「边的编号是否属于 [l,r]」，然后发现只要两个不满足其一，这个边就没有贡献了。

这不失为一个非常优秀的性质，它允许我们将限制条件转化为让 l \le \min(u,v,label) 且 \max(u,v,label) \le r，其中假设边 (u,v) 的编号为 label。

现在考虑建系，设横轴为 \min 维，纵轴为 \max 维，此时对边的询问就变成了在一个 2-side 矩形里面数点。

时间复杂度 O(n \log n)。

BZOJ 4212 神牛的养成计划

一个经典的 trick 是对字符串建立 Trie 树，然后转化到 DFS 序上的点。

此时我们不难想到对模式串正着建个 Trie，记为 T_0，反着建个 Trie，记为 T_1，然后查询的时候对于串 a 的限制就是在 T_0 上跑，对于串 b 的限制就是在先翻转，然后在 T_1 上跑，然后查询满足在 T_0 中 DFS 序范围为 [d_a,d_a+siz_a]，在 T_1 中 DFS 序范围为 [d_b,d_b+siz_b] 的有效交的大小。

这个时候我们开始建系，考虑设横轴为 T_0 的 DFS 序列，纵轴为 T_1 上的 DFS 序列，则每个字符串的每个字符都对应了平面上的一个点，然后查询就是在 4-side 的矩形内数点。

由于是强制在线，所以把扫描过程扔到主席树上，此时依然是单 \log 的。

时间复杂度 O(L_2 + m\log L_1)。

UOJ 637. 【美团杯2021】A. 数据结构

Trick Point：

这种查有多少元素的题一般都考虑利用不同值对答案贡献独立的性质。

先考虑对每个元素计算一下其对哪些询问有贡献，然后使用数据结构批处理贡献。

考虑每个元素对答案的贡献，有一种常见方法是考虑对于什么询问这个元素对答案没有贡献。

如果一个出现了 k 次的数所影响的范围可以用 O(k) 个矩形表示出来，我们也就解决了这个问题，因为 \sum k = n。

由于一个数 x 出现多次和出现一次的情况是完全一样的，所以不妨考虑一下什么时候这个数它消失了。简单而快速的，我们知道只有两个条件：

  1. 数 x 全都被 +1 了。
  2. 数 x-1 全没被 +1。

现在需要将这些限制条件转变成平面上的限制条件，考虑建系，设横轴为序列维（对应询问 l），横轴也为序列维（对应询问 r）：

  1. 数 x 全部被 +1 了。

    简单的，维护一下数 x 第一次出现的位置 L 和最后一次出现的位置 R，那么显然当询问 [l,r] 存在 l \le L 且 r \ge R 的时候对区间没有贡献。

  2. 数 x-1 全没有被 +1。

    考虑数 x-1 相邻两次出现的位置 i,j，则显然的是 [i+1,j-1] 这一段内是不存在 x-1 的。

    对应到二维平面上，就是矩形 [i+1,j-1] \times [i+1,j-1]。

    换句话说，所有 x-1 不出现的位置构成了 O(cnt_x + 1) 个矩形。

然后不难发现，限制 1 的本质上就是将限制 2 算出的矩形切掉了一部分，所以不影响渐进意义上的矩形个数。

考虑此时的询问就变成了平面上的若干点，这时候我们将问题转化为上面的「基础问题」，做删贡献扫描线即可。

时间复杂度 O((n+m)\log n)。

百度之星 2021 初赛第三场 1008

给定一个长度为 n 的序列 A，下标从 1 到 n，有 m 次查询操作，每次给出一个区间 [l,r]，求一个子区间 [l',r']，满足 l \le l' \le r' \le r，使得 [l',r'] 中的颜色数比 [l,r] 中出现的颜色数少，且其长度 r'-l'+1 最大。如果 l' > r'，我们认为没有值在 [l',r'] 中出现过。

首先感谢高效率原题自动机 do_while_true 为我找到了原题链接。

考虑答案会是什么样子，不难想到要么是一个前缀，要么是一个后缀，要么是一个中间一部分的子区间。

前缀咋做呢，显然的，只要找到了最靠右出现第一次出现的那个数的位置，在这个位置之前的都是合法的答案，后缀同理。这两个「扫描线 + 树状数组 + 倍增」都是轻松做的，在这里不多赘述。

至于「中间一部分的子区间」这一类情况，套用 UOJ 637 那道题的 trick，考虑「以 r 为横坐标，l 为纵坐标」建系，设 a 为颜色 c 出现的位置之一，b 为其后继，则任何一个严格包含 [a+1,b-1] 的区间都可以去除区间 [a+1,b-1] 以外的部分来获得 b - a - 1 的贡献，然后可以这样做的 L,R 只有 L \in [1,a], R \in [b + 1, n]，对应到平面上就是一个 2-side 矩形，扫描线上维护「后缀 \max(x, a_i)，单点查」即可，发现这个玩意可能要 Segbeats，进一步观察性质，发现每一次修改的后缀都不一样，然后维护的信息可以对偶成「单点修改，前缀 \max」，所以用树状数组维护即可。

时间复杂度 O((n+m)\log n)。

UVA1608 Non-boring sequences

唯一的难点在于建系。

假设一个数的前驱、后继的位置为 i,j，考虑这个数能支配的最长区间是多大，则不难发现是 [i+1,j-1]，不然的话就会出现相同的两个数。

然后你发现如果这样直接在序列上统计的话似乎不直观，而且好像还算重了很多部分，所以不妨把它放到二维平面上。具体的讲，就是以横轴为序列维，纵轴也为序列维建系，然后此时一个点所支配的就是一个矩形 [i+1,j-1] \times [i+1,j-1]，则此时考虑做「矩形面积并」，然后判断算得的面积是否与整个平面的面积 \dfrac{n(n+1)}{2} 相等即可。

时间复杂度 O(n\log n)，注意别忘了这个题还是多测。

经典问题

有一个长度为 n 的序列，有 m 次询问，每次询问一个区间，问区间上出现奇数次数的数的异或和为多少。

要求线性。

根据异或的性质，发现当一个数异或偶数次自己，贡献为 0。

所以原问题可以转化成区间异或和，考虑做异或前缀和即可。

时间复杂度 O(n+m)。

不那么经典的问题

有一个长度为 n 的序列，有 m 次询问，每次询问一个区间，问区间上出现偶数次数的数的异或和为多少。

要求单 \log。

根据「经典问题」，我们知道了出现奇数次怎么做，但是感觉偶数次似乎很难做的样子。

考虑正难则反，由于异或的性质「自己为自己的逆运算」，所以只要能够统计出「区间内出现的数的异或和」，然后再异或上「区间异或和」，我们就得到了出现偶数次数的数的异或和。

那对于这种区间颜色单贡献有关的部分，容易想到「HH 的项链」，显然这个题可以类比「HH 的项链」，当我们扫描到一个数的时候，让这个数的前驱的贡献变为 0，然后做查询即可。

时间复杂度 O((n+m) \log n)。

CF1083D The Fair Nut's getting crazy

假设 a \le c \le b \le d，不难发现此时的 a 为 \le c 里面的一段后缀，d 为 \ge b 里面的一段前缀。

考虑维护序列 A 每个位置值的前驱和后继，记为 pre_i 和 suf_i，此时进一步缩放 a 和 d 的范围，则 a 的可能取值被限制在了 (\max_{i=c}^b pre_i,c]，d 被限制在了 [b,\min_{i = c}^b suf_i)，现在我们满足了题目的所有要求，此时答案为 (c - \max_{i=c}^b pre_i) \times (\min_{i=c}^b suf_i - b)，将式子拆开，得到 c\min - cb - \min\max + b\max。

建系，设横轴为 b 的可能取值，纵轴为 c 的可能取值，扫描线在横轴上从左向右跑，跑的同时维护两个维护了 pre 和 suf 的后缀最大值的单调栈，扫描线向右扩展的时候向两个单调栈分别加入的 pre_{b'} 和 suf_{b'}， 考虑此时会弹出若干元素，这个时候计算这些元素的贡献即可，具体地说，就是线段树上区间更新 \min 部分和 \max 部分，简单的，考虑打两个标记 mntag 和 mxtag 即可，然后每一次做一次全局查询加到 ans 里面即可。

时间复杂度 O(n \log n)。

CF793F Julia the snail

考虑离线，设横轴为询问右端点，线上维护询问左端点，设 f_i 表示从 i 开始能走到的最高的距离，线上维护数列 f，然后不难发现遇到一个新的绳子时所有 f_i\ge l 的地方全部都能变为当前的 r，然后询问变成单点询问即可，考虑这个东西做「Segment tree beats」即可。

由于没有区间加，所以时间复杂度 O((n + q) \log n)。

CF407E k-d-sequence

首先特判 d = 0，做法简单，找到最长的连续段即可。

现在考虑 d \not= 0，发现一个数列想要满足题目条件必须满足以下条件：

  1. 区间内所有数模 d 均为一个数。
  2. 不出现重复的数字。

可以将序列分成若干个「模 d 连续段」，这样的话第一个限制就消失了。

现在需要对每个连续段考虑限制 2,3 怎么做。

考虑扫描线扫描序列右端点，线上维护序列左端点，即在线上维护 \dfrac{\max - \min}{d} - r + l - k，考虑 k 可以当做常数，l,r 可以被转化为区间加，难点在于前面，简单的，用一个单调栈维护一下 \max 和 \min 即可，在弹出的时候做区间加就好了，查询二分一下即可。

考虑限制 2，假设当前右端点位置为 r，上面的数位 a_r，那么和 a_r 相同的位置必定是左端点不能跨越的，这样使得这个东西变成了一个「首端删除、末端加入」的操作。

综上，我们需要在线上维护「区间加、首端删除、末端加入，区间上二分」这些操作，简单的，用线段树搞一下就好了。

时间复杂度 O(n \log n)。

CF453E Little Pony and Lord Tirek

考虑每一次询问都会导致一部分直接推平，然后推平后就成了简单的分段函数型（一次函数与常值函数）了，我们设时间为每个位置的颜色，则此时每一次区间查询就被我们转换到区间染色，这样贡献被拆成了若干染色段的同时也方便我们维护时间差。

考虑 m,r 的范围比较小，仔细算算我们最多最多只需要维护 1e5 长度的时间，这样就好办了，考虑扫描线扫描序列维，然后分段函数就被我们变成了在时间维上的等差数列加（当函数值 \le m 时）和区间染色（当函数值 \ge m 时），然后查询是一个单点的查询，所以不难想到进行一个差分，然后将「等差数列加」和「区间染色」转变成「区间加」和「单点加」，然后将单点查变为「两次前缀和的差」。

时间复杂度 O((n+q)\log n)。

P5490 【模板】扫描线（矩形面积并）

（好好好，现在才做模板题是吧）

由于出题人直接把坐标系怼在我们脸上了，只需要考虑扫描线的部分就好了。

把矩形拆成入边和出边，然后在 x 轴上跑扫描线，此时在线上维护「区间 \pm1，全局 >0 位置数」，考虑使用线段树来维护。

这里的线段树略微有一点点技巧，我们可以维护区间 \min 值和区间 \min 值出现次数，如果区间 \min 值为 0 的话，此时出现次数就是 0 的出现次数，那么正数位置数就是拿总长度减去即可，如果区间 \min 值不为 0，那就更好办了，说明整个区间都是正数，直接返回总长度。

未知渠道获取的题

有 n 个矩形和 q 次询问。

每次询问给你一个矩形，问这个矩形与 n 个矩形之并的交的面积。

原版要求强制在线，不过个人认为没有必要，离线就好。

要求单 \log。

承上启下的好题了，给下面打个基础 qwq。

在 P5490 中，我们知道了怎么做矩形并，首先将矩形差分，然后线上维护「区间 \pm 1，全局 0 的个数」。

然后这个题特别有意思，先形式化一下题意，此时查询操作为「查询询问矩形内 \gt 0 的位置的个数」，考虑直接做不好办，正难则反，数出「询问矩形内 0 的位置的个数」，然后拿询问矩形的面积一减就好了。

依旧考虑扫描线，由于查询信息可差分，直接差分成 3-side 矩形，然后问题变成了维护区间 0 的个数的历史和，线段树简单做就好。

那怎么强制在线呢，依旧是简单的，将扫描过程丢到主席树上，此时可能需要一个标记永久化，由于原题还需要离散化，所以需要还有一个垃圾分讨……反正很恶心就对了/tuu。

注意，这个问题还有一个对偶版本（应该可以这么叫吧）是这样的：

有 n 个矩形和 q 次询问。

每次询问给你一个矩形，问这个矩形与 n 个矩形的并的面积。

两者本质上等价，只不过一个是需要拿询问矩形的面积减一下，一个直接就是答案，如果哪场模拟赛出了这个问题，可以直接爆锤出题人 /cf

可供练习的题：

  1. P5070 [Ynoi2015] 即便看不到未来
  2. CF799F Beautiful fountains rows

区间子区间问题

给你一个序列，每次询问区间有多少个子区间满足某个条件。

遇到这类问题，通常以两轴都为序列维建系（横轴为 l，纵轴为 r），把区间转化为二维平面上的点 (l,r)，把询问区间转化为矩形。

不过由于区间有个性质是 l\le r，在平面上反馈过来的就是只有一个半平面才有贡献，所以我们所说的「矩形」具体的讲应该是一个「三角形」的样子，不过我们还是可以把它看成 2-side 矩形。

问题就被转化为查询 y 轴上的一个区间从 x = 1 到 x = now 这段时间中，总共有多少位置满足条件，使用一个能够维护历史信息的数据结构维护即可。

如果刚开始不能理解的话（像我一样），可以尝试这样理解：

我们对 y 轴上的每个位置 i 维护当前是否合法的值 a_i。

然后再给每个位置 i 引入一个计数器 cnt_i。

每次扫描线向右侧移动的时候，就是在进行全局 cnt_i \gets cnt_i +a_i 的操作。

P3246 [HNOI2016] 序列

一个比较经典的问题，如果看懂上面内容的话就可以一眼秒了。

首先将区间转化为平面上的点，即建系，横坐标为 l，纵坐标为 r，然后考虑每一个最小值支配的区域，假设当前序列的最小值 a_{\min} 的位置为 x，则能够发现任何包含了 x 位置的区间其贡献都是这个数，对应到平面上就是一个 L \le l \le x 且 R \ge r \ge x 的 4-side 矩形，其中 L,R 是当前序列的左右端点位置。

如果你笨一点的话，可以使用分治将所有矩形预处理出来，如果你不想被别人说笨蛋的话，也可以使用单调栈维护。

不难发现查询是一个 4-side 矩形，考虑差分，将其变成 3-side 矩形，发现线上需要维护一个「区间覆盖，区间查询历史版本和」这样的操作，然后这个东西可以转换，变成「区间加，区间和」，线段树普通维护即可。

当然这个问题存在更牛逼的「 强制在线 + O(1) 查询」，且也是一个挺好的 trick，不出意外的话以后会聊到。

时间复杂度 O((n + q)\log n)。

CF997E Good Subsegments

（被析合树橄榄了）

转化一下题意先：

给定一个长度为 n 的排列 P，每次查询区间 [l,r] 中有多少子区间 [l',r'] 满足 \max_{i=l'}^{r'}p_i-\min_{i=l'}^{r'}p_i = r' - l'。

考虑套用上面写的套路，将每个区间表示为二维平面上的点 (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

问题转化：

区间有多少子区间颜色数为奇数 \iff 区间每个子区间颜色数\bmod 2 的和。

依旧是考虑将区间转化为平面上的点，建系，让横轴为序列维（对应询问 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)。

可供练习的题：

  1. P8868 [NOIP2022] 比赛
  2. P9747 [KDOI-06-S] 签到题

对一维分治

有些时候，我们所维护的信息不能差分，这个时候就需要祭出我们的分治。

考虑对一维度分治后，此时将一个 4-side 矩形变成两个 3-side 矩形（考虑从中间劈开，然后变成两个开口相对的 3-side 矩形），跑两边扫描线，就可以做到只有插入没有删除了。

由于分治每一次处理所有跨过分支中心的矩形，然后在向下继续分治，所以复杂度会多一个 \log，复杂度证明请类比归并排序。

P6109 [Ynoi2009] rprmq1

由于这个题实在是太毒瘤了，这里就不放题解了，大家自己做做就好 /dk

二维扫描线

我们发现，一维扫描线是对某个维度排序，每次查询 [1,l] 的信息，然后沿着从 1 到 n 的路径扫描全部的询问。

那啥是二维扫描线呢？套用一维扫描线的行为，我们尝试得到二维扫描线的行为：

每次询问 [l,r] 的信息，以一种方式排序，使得经过所有询问，并且复杂度可接受。

实际上就是莫队，这个可以看看 Alex_Wei 的根号算法学习笔记，这里不多赘述。

自由度

考虑一维扫描线 + 一维数据结构可以处理二维静态问题。

然而实际上普通的维护序列问题实际上也属于两个维度。

因为是按照给定的操作序列操作的，这里不乏出现时间的维度。

所以每一次操作都可以看做是一个 3-side 矩形，然后时间一维，序列一维，在时间维上做扫描线，就将二维静态问题转化为了一维动态问题。

于是这启发我们：

扫描线序列维，数据结构时间维

由于序列上的动态操作可以看做成是序列一维，时间一维。

所以在有些情况下我们直接沿着时间维度跑不好处理，这个时候我们就可以考虑在序列维度上做扫描线，然后线上维护时间维。

这种问题一般都是在线上查询一个单点的信息，当然，形势好的话查询区间信息也是可以的。

Comet OJ - Contest #14 D / P8512 [Ynoi Easy Round 2021] TEST_152

直观的看这个题似乎特别不好处理。

不妨从贡献的角度看这个题，把「经过操作序列上 [x,y] 的操作后形成的最终序列上每个位置的和」给拆成「每个时间点对最终序列的贡献的和」。

这会产生两个性质：

  1. 某个时间产生的贡献会随着时间的流逝逐渐消失，换句话说，时间点 i 产生的贡献是不增的。
  2. 时间点 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. 遇到操作 1 时：直接交换两个位置的 vector，ODT 上交换两个位置的颜色。
  2. 遇到操作 2 时：ODT 上区间染色 1，然后对每一个颜色为 0 的位置依次处理完询问，并清空 vector。
  3. 遇到操作 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] 中最靠右的最大后缀和的位置，证明如下：

先证明此时空了：由于我们是最大后缀和，所以这之前必定是空的，否则我们就可以通过左端点向右扩张来增大我们的后缀和。

在证明此后不空：假设 x 时刻是最大后缀和左端点， y 时刻队列空了，x \lt y，那么必然出现了 [x,y] 的和 \lt 0，我们的最大后缀和一定不会去选择一个负数的前缀，所以该情况不可能出现。

由于会出现单点 -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)。

当然，如果你不是很会怎么单 \log 在线段树的一个区间上二分，你可以像我一样来一个笨的方法，就是先区间查出 [1, t-1] 位置上的 push 和，然后把他丢进 pop 量里就可以了。

别忘了还原消减操作！！！

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 上，证明如下：

假设 h 时刻被制裁，那么如果 t 时刻还想被制裁，则必须要保证时间序列上 t 位置上的数 < -\max(0, \sum_{i=h+1}^{t-1} time_i)，否则一定不会被制裁。

这就意味着如果你选上了一段和为非负数的区间，那么必然要选其后面的那一个被制裁的地方，此时才能保证当前前缀和更小，否则一定不会选那一段区间。

现在考虑加上上界，不难发现下面这个性质：

综上，得「相邻的上下界触碰事件」之间区间的和的绝对值一定 \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)。

计算几何中的扫描线

回归扫描线的本质，实际上就是拿一条线去扫平面来获得所需要的信息。

因此较为显然的，我们也可以将扫描线用在计算几何中。

通常的套路是维护扫描线与几何图形截点的位置，与几何图形下一个拐点的位置。

由于我的计算几何很菜，所以只能说两个比较简单的题目。

交点检测

给定平面上 n 条线段，输出所有交点的位置。

保证输出量 \le 10^5。

扫描线扫描 x 轴，线上维护纵轴，也就是每个线段与扫描线的交点。

这样有了一个较好的性质，就是如果线段 l 要与其他线段产生交点，必定先与在扫描线上的相邻线段有交点。

那么此时维护扫描线上相邻线段什么时候发生交点，计算交点并在扫描线上交换两个线段的位置。

由于是线段，所以还需要维护线段的加入事件和删除事件。

综上，用平衡树维护一下上述操作就好了，设交点数为 o，则时间复杂度为 O((n + o)\log n)。

平面图点定位

给定平面上 n 条直线，将平面划分为了一个平面图

你需要建出这个平面图。

类比交点检测，发现如果出现了交点，则说明这个的一个区域被封闭了。

这样一直做就可以找到所有区域以及相邻区域。

设区域数为 o，则时间复杂度为 O((n + o)\log n)。

可供练习的题：

  1. P3268 [JLOI2016]圆的异或并
  2. P5525 [Ynoi2012] WC2016 充满了失望
  3. P6106 [Ynoi2010] Self Adjusting Top Tree

树上扫描线

考虑在序列上的时候我们的询问会转化为 O(1) 个矩形。

现在问题上树，不难想到将树上问题转化为序列上的问题，故进行树链剖分。

这里利用了一个树链剖分的一个非常优秀的性质：「树上的任意一条路径划分成不超过 O(\log n) 条连续的链」。

由于这一个性质，我们将拆分出来的链分别做矩形，此时最多会出现 O(\log n) 个矩形。

如果考虑路径上点之间的关系的话，则最多会出现 O(\log^2 n)。

然后我们就在原先复杂度基础上多了一个或者两个 \log，复杂度在大部分情况下依旧是可以接受的。

未知渠道获取的题

定义一个点对 (i,j)(i \not= j) 是好的当且仅当：

\exist k \in N^{*},\qquad \lfloor\dfrac{i}{k}\rfloor = j

给定一棵 n 个点的树，树上点的权值互不相同，点权的值域为 m，共有 q 次询问。

每次询问给定一个路径 (x,y)，问路径上多少个点对 (u,v) 满足 (a_u, a_v) 是好的。

考虑整除分块，预处理出所有符合条件的点对。

建系，设横纵坐标都为序列维（dfn 维），则点对变成平面上的点。

对于每个路径，预处理所有可能的询问矩形，即两个链组合在一起组成一个询问矩形，由于树链剖分的性质，不难发现矩形数是 O(q\log^2 n) 的。

然后现在的问题就变成一个简单的二维数点，时间复杂度 O(q \log ^ 3 n + n \sqrt m \log n)，足以通过该题，由于常数极小，把标算给锤了。

可供练习的题：

  1. P1600 [NOIP2016 提高组] 天天爱跑步