AT_acl1_a Reachable Towns

Accelessar · 2025-02-15 23:05:13 · 题解

考虑先按 x 排序，那么问题可转化成这样：

• 对于 i\lt j，若 y_i\lt y_j 则在 i,j 间连一条无向边。求每个点所属连通块大小。

发现这个形式几乎和 ARC187B 一致，有以下结论：

• 每个连通块都是一个区间。
  证明：假设存在一个连通块不包含 i，但在 i 左侧和右侧都有点。则必然存在 u,v 使得 u\lt i\lt v\land y_u\lt y_v。简单讨论 y_i 的取值，发现无论取何值都至少和 u,v 中的一者有连边，故假设不成立。
• 证明：显然 $i,i+1$ 不连通意味着 $i$ 所属连通区间的最小值大于等于 $i+1$ 所属联通区间的最大值。从而可以推广得到联通区间的值域是递减的，所以 $i$ 为分割点的充要条件可以弱化为前缀最小值大于等于后缀最大值。

那么可以 O(n) 求出所有分割点，也即求出了所有连通块。

submission.