扫描线好题集

· · 算法·理论

引言：本想就加在好题集锦里面，但好像出现频率特多，单独拉出来。

扫描线问题的核心就是去确定数据结构维护的是什么东西，原则是在每次算增量的时候要好算，可以是总次数的均摊 O(n)，或是单调队列的合并均摊 O(n)，或是一些奇妙的单次 O(logn)。

[20241017] 开发者选项

这题扫描线还是比较一眼的，主要是维护的东西不太容易想到。

首先可以对条件进行一个转化。对于每一个点，可以维护包含它的区间的左端点的最大值，记作 pt_i。发现，对于指定的区间，当某个点未被覆盖时，pt 值为0，当覆盖它的区间会超过当前询问的左端点时，pt_i<l。由此，对于一个区间，合法的条件为 min_{l\le i\le r}\{pt_i\}=l。然后就可以在动态移动右端点的同时，用一颗线段树维护序列的 pt ，区间取 max，区间求 min。

可以发现，此题将区间的信息转化为每个点的信息。区间贪心的条件是选一个尽量长的区间，使得它的左端点不超过要求的左端点，这样的话对于不同的左端点决策是不同的。然而我们对于点的贪心就是覆盖区间的最大左端点，也许在某一个询问中会用到某一个覆盖当前点左端点更小的区间，但它不影响当前点的覆盖情况，会在前面的点考虑。

tip：区间覆盖信息转化为点的最值。

[Ynoi2012] NOIP2015 充满了希望

第一道Ynoi，纪念一下。

数据范围 1e6，直接排除 log^2n 和\sqrt n。发现只有操作2会有赋值，操作1的交换十分鸡肋。不强制在线，考虑扫描线。发现对于每个数，只关心最后一个覆盖他的区间是谁，可以通过一颗线段树记录每个点最后覆盖区间的标号（有可能与别的点交换，则交换两个点最后覆盖的区间标号）。又能发现对于每个点，要么是被最后一个覆盖操作的值改变，要么为0，那么对于某个询问 l,r ，只有当某个点的最后覆盖的标号 >= l 才有才会被算进答案。那么对于询问就可以通过树状数组维护一个后缀和就是答案呢。时间复杂度 O(nlogn)

tip：将存值信息改成存标号，这样会多记录一个时间点。

[20241112] 点支配集

呜呜，计数题永远的伤。

对于此类计数题，常用的思路就是，在枚举到某个点时，考虑它选与不选分别的贡献，不选的时候是可以继承前面的值，选的时候可以将一些区间覆盖。考虑数据结构维护什么值，想过 j 位存用 j 以前的区间覆盖完前 j 的方案数，然而无论如何转移都会算漏或算重。可以发现这样的设计没有很好的利用扫描线的特点。于是改状态 j 为用前 i-1 个区间覆盖到前 j 个区间（ j+2 后面无所谓，也就是一个未被覆盖的区间为 j+1）的方案数。i不选直接继承，考虑 i 选的影响，对于 j，r_{j+1}<l_i，i 选了是没有影响的，还是自加。对于 j,r_{j+1}>l_i，i 选之后会连到 i 能覆盖的最远区间，又因为右端点单调，所以相当于后面所有的状态都会加到一个点上面。所以需要维护的就是区间乘（自加），区间求和，单点加，线段树解决，时间复杂度 O(nlogn)。