标签:扫描线
5 个条目
-
概念 事件模型
把事件抽象为偏序集中的元素,用转移映射和线性扩展描述它与扫描模型的交互;坐标、类型、载荷只是表示层。
2026-11-12 -
概念 扫描模型
把偏序条件线性化,增量维护充分统计量,在切点读取查询;状态可以是覆盖重数、DP 表或单调前沿。
2026-11-12 -
概念 二维支配最值
给定平面点集,对每个点求其严格右上方点中 x+y 的最小值;按 x 降序扫描,用线段树维护后缀最小值。
2026-11-12 -
区间内选两个数,用最少乘除质数操作使乘积为完全平方;按右端点扫描,维护每个 gcd 的最大下标与答案前沿。
2026-11-12 -
题目 矩形并
给定若干轴对齐矩形,求并的面积和周长;按 x 扫描,用线段树维护 y 方向覆盖长度与连通分量数。
2026-11-12