CF1920F2 题解

EuphoricStar · 2024-01-15 07:23:31 · 题解

首先需要知道的一个 trick：判断一个点是否在一个闭合回路内部，从这个点向任意方向引一条射线，若不考虑相切，那么和回路的交点为奇数时这个点在回路内部，否则在外部。

那么这题要判断一个回路是否包含全部的 island，可以找到任意一个 island 向右引一条射线。

给每个点增加一个状态 (x, y, 0/1) 表示当前走到 (x, y)，穿过了偶数或奇数次射线。那么一次询问的本质是找到一条 (x, y, 0) \to (x, y, 1) 的一条经过点权最小值最大的路径（可以多源 bfs 求出任意一点 (i, j) 到最近的 v 的距离 d_{i, j}，(x, y, 0/1) 的点权就是 d_{x, y}）。

上面那个问题显然给每条 (u, v) 赋权 \min(val_u, val_v)，就可以建 Kruskal 重构树查 LCA 解决。

建图就对于一个 (x, y)，如果它在射线上就视为 (x, y) \to (x + 1, y) 和射线新增了一个交点。

时间复杂度 O((nm + q) \log nm)。

code