题目理解

平面上有 $n$ 个喷泉，坐标都是偶数。需要在这些喷泉之间建造长度为 $2$ 的道路（水平或垂直），使所有喷泉连通（形成生成树）。每条道路必须分配一个长椅，长椅坐标均为奇数，且只能放置在特定位置。长椅位置不能重复。

关键约束

1. 道路限制：只能连接曼哈顿距离为 $2$ 的喷泉（水平或垂直相邻）
2. 长椅位置：长椅 $(a,b)$ 只能分配给以下四种道路之一：
   • $(a-1,b-1) \leftrightarrow (a-1,b+1)$
   • $(a-1,b+1) \leftrightarrow (a+1,b+1)$
   • $(a+1,b+1) \leftrightarrow (a+1,b-1)$
   • $(a+1,b-1) \leftrightarrow (a-1,b-1)$
3. 连通性：所有喷泉必须通过道路连通

---

核心观察

1. 坐标奇偶性分析

• 喷泉坐标：$(2x, 2y)$
• 长椅坐标：$(2x+1, 2y+1)$
• 每个 $2\times 2$ 的正方形有：
  • 4个喷泉可能位置（偶数坐标）
  • 1个长椅位置（中心奇数坐标）

2. 图模型转化

将问题转化为图论问题：

• 顶点：$n$ 个喷泉
• 边：可能的道路连接（曼哈顿距离为 $2$ 的喷泉对）
• 目标：选择 $n-1$ 条边构成生成树，为每条边分配一个长椅

3. 二分图结构

可以将平面划分为黑白格子：

• 黑格：满足 $(x/2 + y/2)$ 为奇数的 $2\times 2$ 正方形
• 白格：满足 $(x/2 + y/2)$ 为偶数的 $2\times 2$ 正方形

每个长椅只能放在一个 $2\times 2$ 正方形的中心，且每个正方形最多放置一个长椅。

---

算法思路

1. 基本框架

使用并查集维护连通性，贪心地尝试连接喷泉，同时为每条边分配长椅。

2. 关键策略

1. 预处理邻接关系：

   • 使用哈希表记录每个坐标对应的喷泉编号
   • 枚举所有可能的 $2\times 2$ 正方形

2. 系统化尝试连接：

   • 对每个 $2\times 2$ 正方形，根据其坐标奇偶性决定优先连接方式
   • 黑格优先尝试垂直连接，白格优先尝试水平连接
   • 避免形成环路（使用并查集）

3. 长椅分配：

   • 每个 $2\times 2$ 正方形中心唯一对应一个长椅位置
   • 成功连接一条边时，自动分配对应正方形的中心作为长椅

3. 算法步骤

1. 初始化并查集，每个喷泉独立
2. 枚举所有可能的 $2\times 2$ 正方形（以左下角坐标 $(x,y)$ 表示）
3. 对正方形按坐标排序并去重
4. 对每个正方形：
   • 根据 $(x/2 + y/2)$ 的奇偶性选择连接策略
   • 尝试连接正方形内的喷泉对（检查喷泉存在且未连通）
   • 成功则记录边和长椅位置
5. 检查所有喷泉是否连通
   • 连通：调用 build 报告方案
   • 不连通：返回 $0$

---

算法正确性证明

1. 长椅位置合法性

每个长椅位于 $2\times 2$ 正方形中心 $(x+1, y+1)$，其中 $(x,y)$ 为正方形左下角坐标（偶数）。由长椅分配规则，只能分配给该正方形四条边之一，算法中每次连接确实使用正方形的一条边。

2. 无冲突分配

算法按正方形处理，每个正方形最多产生一条边，因此每个长椅最多被分配一次，满足长椅位置互不相同的要求。

3. 连通性保证

算法使用并查集确保不形成环路，最终检查是否形成生成树。如果存在解，该贪心策略能找到一个解（基于坐标扫描的顺序性）。

4. 完备性

如果算法返回 $0$，则确实不存在合法方案。因为算法系统地尝试了所有可能的连接方式（优先策略覆盖了所有可能性）。

---

复杂度分析

时间复杂度

1. 预处理：$O(n)$
   • 建立坐标到喷泉编号的映射
2. 正方形枚举：$O(n)$
   • 每个喷泉生成 $4$ 个正方形，去重后仍为 $O(n)$
3. 连接尝试：$O(n\alpha(n))$
   • 每个正方形尝试常数次连接操作
   • 并查集操作近似常数时间
4. 总复杂度：$O(n\alpha(n))$，满足 $n \leq 2\times 10^5$ 的限制

空间复杂度

1. 坐标映射：$O(n)$
2. 正方形列表：$O(n)$
3. 并查集：$O(n)$
4. 结果存储：$O(n)$
5. 总空间：$O(n)$，满足内存限制

---

实现细节

1. 数据结构设计

// 坐标映射：快速查找喷泉编号
map<pair<int, int>, int> point_to_index;

// 并查集：维护连通性
vector<int> parent;

// 结果存储
vector<int> u, v, a, b;

2. 关键函数

• find(x)：并查集查找
• union_sets(x, y)：合并两个集合
• try_connect(p1, p2, bench_x, bench_y)：尝试连接两个喷泉

3. 扫描顺序

按正方形左下角坐标 $(x,y)$ 排序，确保系统化处理所有可能性。

---

算法标签

• 贪心算法
• 并查集
• Hashing
• 坐标变换
• 生成树
• 构造算法
• 离散化与扫描

---

总结

本题将几何约束转化为图论问题，通过巧妙的坐标分析和系统化的贪心策略，在 $O(n)$ 时间内构造解决方案。关键在于利用 $2\times 2$ 正方形的结构特性，将长椅分配与道路连接统一处理。算法简洁高效，充分利用了题目中坐标奇偶性的特殊性质。