扫描模型

把偏序条件线性化,增量维护充分统计量,在切点读取查询;状态可以是覆盖重数、DP 表或单调前沿。

标签 数学 / 扫描线 / Sweep line / 离线 / 偏序 / DP

定义

设 𝑇={1,…,𝑁},表示有限全序时间轴。

𝑆 是集合,表示状态空间,初始状态 𝑠0∈𝑆。

对每个 𝑡∈𝑇 给定转移 𝑢𝑡:𝑆→𝑆。状态序列定义为

𝑠𝑡≝𝑢𝑡(𝑢𝑡−1(…𝑢1(𝑠0)…)),

一个查询 𝑞∈𝒬︀ 由二元组 (𝑡𝑞,𝑄𝑞) 表示,其中 𝑡𝑞∈{0,…,𝑁} 是切点,𝑄𝑞:𝑆→𝑉 是泛函。

查询 𝑞 的答案为 𝑄𝑞(𝑠𝑡𝑞)。

记

ℳ︀=(𝑇,𝑆,𝑠0,(𝑢𝑡)𝑡∈𝑇,(𝑡𝑞,𝑄𝑞)𝑞∈𝒬︀).

称这样的数据为一个扫描模型。扫描线算法就是构造一个扫描模型,使 𝑄𝑞(𝑠𝑡𝑞) 等于原问题的答案,并且 𝑢𝑡 的更新与 𝑄𝑞 的求值可由数据结构高效实现。

构造扫描模型

构造扫描模型通常需要定义一个基于状态空间 𝑆 和全序轴 𝑇 的事件模型

ℰ︀=(𝐸,⪯,𝑈,ℓ),

其中 𝐸 是事件集,⪯ 是事件上的偏序,𝑈:𝐸×𝑆→𝑆 把事件作用到状态上,ℓ:𝐸→𝑇 是 线性扩展。若 𝑒𝑡=ℓ−1(𝑡),则扫描模型的转移为

𝑢𝑡(𝑍)=𝑈(𝑒𝑡,𝑍).

事件 𝑒 对扫描模型只暴露三项:它在 ⪯ 中的位置、转移 𝑍↦𝑈(𝑒,𝑍),以及它是否属于查询的依赖集。

构造时需要确定:

  1. 事件集 𝐸 与偏序 ⪯;
  2. 状态空间 𝑆、初态 𝑠0 与转移 𝑈;
  3. 线性扩展 ℓ:𝐸→𝑇,从而得到 𝑢𝑡;
  4. 查询 𝑞=(𝑡𝑞,𝑄𝑞) 与依赖集 𝐷𝑞⊆𝐸。

查询切点必须满足

𝐷𝑞⊆ℓ−1({𝜏∈𝑇:𝜏≤𝑡𝑞}),

即所有依赖事件都已在 𝑞 之前处理。同一坐标可能有多个事件,需要用类型优先级或编号把它们排成线性扩展;这决定严格/非严格条件和读写顺序。

状态与充分性

设 ℰ︀𝑡=ℓ−1({𝜏∈𝑇:𝜏≤𝑡}) 是前 𝑡 个事件构成的前缀。状态 𝑠𝑡 是 ℰ︀𝑡 的充分统计量:若两个前缀有相同的 𝑠𝑡,则所有切点为 𝑡 且 𝐷𝑞⊆ℰ︀𝑡 的查询答案相同。等价地,每个这样的查询答案都只依赖于 𝑠𝑡。

状态不限于几何截面;它是前缀的充分统计量,截面只是其特例。若把更新生成的变换幺半群记为 𝑈,则 𝑆 是 𝑈-集,扫描是前缀词的作用。𝑈 不必是群;min、max、并集等交换幺半群都适用,只有删除操作需要逆元。

常见误解

  • 把扫描线等同于矩形并或计算几何:后者只是覆盖型状态的一个实例。
  • 把状态等同于截面:状态是充分统计量,截面只是其特例。
  • 认为状态必须成群:min、max、并集等交换幺半群即可;只有删除需要逆元。
  • 认为同一时间步内的操作可交换:读写顺序是扫描模型的一部分;矩形周长并、Make Square 都依赖它。
  • 认为扫描线必须在线:扫描线通常是离线线性化,需要预先知道事件与查询。
  • 认为必须按坐标轴排序:任何线性扩展都可以;下标、时间、右端点都常用。
源码位置