二维支配最值
给定平面点集,对每个点求其严格右上方点中 x+y 的最小值;按 x 降序扫描,用线段树维护后缀最小值。标签 数学 / 偏序 / 扫描线 / 问题模型 / 线段树
模型
给定 个点 。若 且 ,称点 支配点 ,也就是 在 的严格右上方。对每个点 ,在所有支配它的点 中求 的最小值:
若没有这样的点,约定 。目标是输出 。
扫描模型
用 事件模型 的记号。取事件集 ,事件 表示插入点 。令 当且仅当 ,取线性扩展
令 ,状态空间
初始状态 对所有 。事件 作用到状态 上,只在 处更新:
若 ,则 。于是状态序列按定义生成,并且
空集取 。
对点 ,取查询 ,切点 为同一 的所有事件之前的切点。依赖集
满足 。令 ,泛函 为
于是
其中 、、。同一 上查询先于插入,保证严格不等式 。
正确性
扫描到切点 时,所有 的点都已插入,而 的点尚未插入。因此状态包含且仅包含 的点;对每个 , 是这些点中纵坐标为 的最小 。查询再限制 ,所以
若没有支配点,最小值在空集上取 。
实现
用线段树按下标 维护 ,支持单点取 和后缀最小值查询。 稀疏时离散化或动态开点。每个点插入一次、查询一次,时间 ,空间 。
变式
- 把 换成任意权值 ,扫描模型不变。
- 非严格支配 、:把查询放在同一 的插入之后,并把后缀查询改为包含 。
- 其他方向:改变排序方向,查询改为前缀或后缀最小值。