问题分析

题目要求调整n座小岛的人数（为1~n的排列），使得“快乐的划水路线”数量最大化。一条路线是快乐的需满足：平行于x轴或y轴、至少经过一个小岛、沿途小岛人数的GCD为1。

核心思路

1. 问题转化：
   每条平行于x轴的路线对应一个x坐标（记为x线），每条平行于y轴的路线对应一个y坐标（记为y线）。目标是最大化满足以下条件的x线和y线总数：

   • 若线（x或y）上只有1个小岛，则该小岛人数必须为1（因单个数字的GCD为自身）。
   • 若线（x或y）上有多个小岛，则这些小岛人数的GCD必须为1。

2. 关键观察：

   • 单个小岛的线：分配人数1可直接使其成为快乐路线。
   • 多个小岛的线：需分配至少两个互质的数（如一个偶数和一个奇数），确保整体GCD为1。
   • 利用二分图模型：将x坐标和y坐标视为二分图的两个节点集，每个小岛对应连接其x和y的边。通过分析二分图的连通性和节点度数，可高效规划人数分配。

3. 构造策略：

   • 优先处理单岛线：识别仅含1个小岛的x线或y线，将人数1分配给该小岛，直接获得2条快乐路线（若该小岛同时属于单岛x线和单岛y线）。
   • 处理多岛线：对于含多个小岛的线，分配包含不同质因数的数（如偶数和奇数），确保它们的GCD为1。利用排列的唯一性，避免重复使用数字。
   • 连通性分析：通过DFS遍历二分图，确保同一连通分量内的数分配满足所有线的GCD条件，最大化快乐路线数量。

详细步骤

1. 坐标预处理：
   对x、y坐标去重，映射为连续编号（便于处理），统计每条x线和y线上的小岛数量（度数）。

2. 二分图构建：
   以x坐标和y坐标为节点，小岛为边，构建二分图。通过并查集（find函数）记录连通分量。

3. 单岛线处理：
   识别度数为1的x线或y线，将人数1分配给对应的小岛，标记该线为快乐路线。

4. 多岛线处理：
   对度数≥2的线，通过DFS遍历连通分量，分配含不同质因数的数（如交替分配偶数和奇数），确保线内所有小岛的GCD为1。

5. 排列验证：
   确保分配的数是1~n的排列，且所有快乐路线的GCD条件满足。

代码解析

• 坐标映射：getx和gety函数将原始坐标映射为连续编号，便于统计和处理。
• 二分图与连通性：通过v和w数组存储二分图的边，find函数维护并查集，识别连通分量。
• DFS遍历：dfs1和dfs2函数用于遍历连通分量，规划人数分配，优先处理单岛线和多岛线。
• 排列构造：getans1和getans2函数生成1~n的排列，确保分配给多岛线的数满足GCD条件。
• 验证：通过gcd函数检查每条线的GCD是否为1，确保结果正确性。

复杂度分析

• 时间复杂度：$O(n \log n)$。坐标映射和排序为$O(n \log n)$，DFS遍历和GCD计算为$O(n)$，整体线性对数级，适合$n \leq 2 \times 10^5$。
• 空间复杂度：$O(n)$，用于存储坐标映射、二分图结构和中间结果。

该方案通过二分图模型和贪心策略，高效构造满足条件的排列，最大化快乐的划水路线数量，兼顾正确性和性能。