浅谈扫描线状物

我看到很多人对于扫描线的理解不够深刻，所以特地来写一篇关于扫描线状物应用的文章。

选了点印象深刻的题目和最近做的。

基础扫描线

扫描线最基本的应用和一般人入坑扫描线都是来自于一个题：求一车矩形面积并。

这个东西你就考虑在 $y$ 轴上从下往上扫，每个矩形会在它的下边界出现，在它的上边界消失，所以只要记录每个时刻消失和出现的矩形是哪些，对着 $x$ 轴建 segtree 做一下即可。

例题#1

首先来看一个比较简单的题。

给定一颗树，点数 $10^5$，定义 $f(l,r)$ 表示仅保留 $l \sim r$ 的点的连通块个数，求 $\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)^k$，其中 $1 \leq k \leq 10$。

我们先来想一下 $k=1$ 的做法。

我们考虑 $f(l,r)=r-l+1-e(l,r)$，其中 $e(l,r)$ 表示仅保留 $l \sim r$ 的边的数量。

我们从打到小扫描 $l$，每次枚举 $l$ 的一个编号大于 $l$ 的儿子 $v$，那么对于 $v \leq r \leq n$，这条边有 $-1$ 的贡献，不难用线段树维护。

再来考虑一般的情况。

问题转化为了区间加 $1$ 或 $-1$，求全局 $k$ 次方和。

不难考虑改为权值线段树，维护 $1 \sim k$ 次方和即可。

复杂度 $O(nk^2 \log n)$。

例题#2（P9893）

问题问的是极差，我们先来看怎么求最大值的最小值。

开个线段树，我们维护 $f_{u,0/1,0/1}$ 表示左端点有没有向左延伸出去以及右端点有没有向右延伸出去的时候，队伍实力的最大值的最小值。

合并不难，枚举中间两个是否连在一起即可。

我们从小到大枚举扫描最小值，表示禁用了 $<v$ 的所有分割方式（实际上是把相关节点权值变成 inf）。

例题#3（P9895）

具体细节可以去看 P9895 【ICPC2018 Qingdao R】 Airdrop。

首先所有人都只会先 y 轴移动，然后再在 x 轴移动。

所以注意到所有的碰撞都在 $y=y_0$ 发生，且只有离 $(x_0,y_0)$ 曼哈顿距离相同的人会撞上。稍稍考虑一下你就会算了 $(x_0,y_0)$。

我们开个线段树，维护一个曼哈顿距离对应的点的个数，具体怎么统计呢？我们从下往上扫 $x$，线段树维护的序列上每一个位置 $x$ 就是 $(x_0,y_0)$ 的答案。

因为每线段树维护的序列上每一个位置，$y$ 方向上的曼哈顿距离是固定的，而扫描 $x$ 的时候每个数和 $x_0$ 的相对位置关系是确定的， 素有这样处理就很方便。

然后就是注意到我们不能扫所有的，只要把 $\bigcup_i[x_i-1,x_i+1]$ 这些点扫到即可。

例题#4（CF2009G3）

作为一道罕见的 div4 有脑子题，这题也使用了扫描线的思想。

首先是根据 G1，我们可以求出每个长度为 $k$ 的区间的答案，此处不再赘述。

我们刻画 $f(l,r)=\min_{i=l}^{r-k+1}t_i$。其中 $t_x$ 指 $[x,x+k-1]$ 的答案。

那么问题等价于询问区间所有子串最小值之和。

我们离线，按照左端点从大到小扫描 $l$，每次对于 $(l,n)$ 取 $\min$ $t_l$，那么答案就是历史和的区间和，不难用神秘线段树解决。

总结

扫描线是一种神奇的思想，它利用了你需要重复加入结构的繁琐，用扫描时间轴或任意一个轴，来达到将一段的存在区间，转化为出现和消失两个时刻，从而达到离线快速处理询问。