二维支配最值

给定平面点集,对每个点求其严格右上方点中 x+y 的最小值;按 x 降序扫描,用线段树维护后缀最小值。

标签 数学 / 偏序 / 扫描线 / 问题模型 / 线段树

模型

给定 𝑁 个点 (𝑥𝑖,𝑦𝑖)。若 𝑥𝑗>𝑥𝑖 且 𝑦𝑗>𝑦𝑖,称点 𝑗 支配点 𝑖,也就是 𝑗 在 𝑖 的严格右上方。对每个点 𝑖,在所有支配它的点 𝑗 中求 𝑥𝑗+𝑦𝑗 的最小值:

𝐴𝑖=min{𝑥𝑗+𝑦𝑗:𝑥𝑗>𝑥𝑖,𝑦𝑗>𝑦𝑖}.

若没有这样的点,约定 𝐴𝑖=+∞。目标是输出 𝐴1,…,𝐴𝑁。

扫描模型

用 事件模型 的记号。取事件集 𝐸={𝑒𝑖:𝑖=1,…,𝑁},事件 𝑒𝑖 表示插入点 𝑖。令 𝑒𝑗≺𝑒𝑘 当且仅当 𝑥𝑗>𝑥𝑘,取线性扩展

ℓ:𝐸→𝑇={1,…,𝑁}.

令 𝑌={𝑦1,…,𝑦𝑁},状态空间

𝑆={𝑍:𝑌→ℤ∪{+∞}},

初始状态 𝑠0(𝑦)=+∞ 对所有 𝑦∈𝑌。事件 𝑒𝑖 作用到状态 𝑍 上,只在 𝑦𝑖 处更新:

𝑈(𝑒𝑖,𝑍)≝(𝑦↦{min(𝑍(𝑦),𝑥𝑖+𝑦𝑖)𝑦=𝑦𝑖𝑍(𝑦)𝑦≠𝑦𝑖)

若 𝑒𝑡=ℓ−1(𝑡),则 𝑢𝑡(𝑍)=𝑈(𝑒𝑡,𝑍)。于是状态序列按定义生成,并且

𝑠𝑡(𝑦)=min{𝑥𝑗+𝑦𝑗:ℓ(𝑒𝑗)≤𝑡,𝑦𝑗=𝑦},

空集取 +∞。

对点 𝑖,取查询 𝑞=𝑖,切点 𝑡𝑖 为同一 𝑥 的所有事件之前的切点。依赖集

𝐷𝑖={𝑒𝑗:𝑥𝑗>𝑥𝑖,𝑦𝑗>𝑦𝑖}

满足 𝐷𝑖⊆ℰ︀𝑡𝑖。令 𝑉=ℤ∪{+∞},泛函 𝑄𝑖:𝑆→𝑉 为

𝑄𝑖(𝑍)=min𝑦>𝑦𝑖𝑍(𝑦).

于是

𝐴𝑖=𝑄𝑖(𝑠𝑡𝑖)=𝑄𝑞(𝑠𝑡𝑞),

其中 𝑞=𝑖、𝑡𝑞=𝑡𝑖、𝑄𝑞=𝑄𝑖。同一 𝑥 上查询先于插入,保证严格不等式 𝑥𝑗>𝑥𝑖。

正确性

扫描到切点 𝑡𝑖 时,所有 𝑥𝑗>𝑥𝑖 的点都已插入,而 𝑥𝑗=𝑥𝑖 的点尚未插入。因此状态包含且仅包含 𝑥𝑗>𝑥𝑖 的点;对每个 𝑦,𝑠𝑡𝑖(𝑦) 是这些点中纵坐标为 𝑦 的最小 𝑥+𝑦。查询再限制 𝑦>𝑦𝑖,所以

𝑄𝑖(𝑠𝑡𝑖)=𝐴𝑖.

若没有支配点,最小值在空集上取 +∞。

实现

用线段树按下标 𝑦 维护 𝑠𝑡(𝑦),支持单点取 min 和后缀最小值查询。𝑦 稀疏时离散化或动态开点。每个点插入一次、查询一次,时间 𝑂(𝑁log𝑁),空间 𝑂(𝑁)。

变式

  • 把 𝑥𝑗+𝑦𝑗 换成任意权值 𝑤𝑗,扫描模型不变。
  • 非严格支配 𝑥𝑗≥𝑥𝑖、𝑦𝑗≥𝑦𝑖:把查询放在同一 𝑥 的插入之后,并把后缀查询改为包含 𝑦𝑖。
  • 其他方向:改变排序方向,查询改为前缀或后缀最小值。
源码位置