AT_acl1_a Reachable Towns

考虑先按

x

排序，那么问题可转化成这样：

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

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

那么可以

O(n)

求出所有分割点，也即求出了所有连通块。

文章操作