一、问题分析与数学建模

1.1 问题本质

这是一道构造 + 图论 + 贪心的综合问题，核心在于如何在满足连通性和可达性约束的条件下，构造字典序最大的建造序列。

问题形式化

给定：

• $n$ 座摩天楼的坐标 $(r_i, c_i)$
• 边界定义：$|r|, |c| > 10^9$

约束条件：

1. 相邻性约束：除第一座外，新建摩天楼必须与已建摩天楼有公共边或公共角
2. 可达性约束：新建摩天楼必须能通过边连接（上下左右四方向）的路径到达边界，路径上不能有其他摩天楼

目标：

• 构造建造序列 $s_1, s_2, \ldots, s_n$
• 模式2：使 $(s_n, s_{n-1}, \ldots, s_1)$ 字典序最大

---

1.2 核心数学观察

观察 1：逆向思维

关键洞察：正向构造困难，采用逆向思维。

定理 1（逆向等价性）：

正向建造序列 $s_1, s_2, \ldots, s_n$ 合法 $\Leftrightarrow$ 逆向拆除序列 $s_n, s_{n-1}, \ldots, s_1$ 满足：

• 拆除 $s_i$ 后，$s_i$ 与"外界"（边界）保持连通
• "外界"是指所有已拆除的位置（空格子）

证明：

• 正向建造时，新建位置必须能到达边界，等价于该位置"周围"有空格子连接到边界
• 逆向拆除时，拆除位置必须不是割点，保证剩余摩天楼仍能到达边界
• 两个过程互为逆操作

---

观察 2：图的二元性

定义两种图：

1. 8-邻接图 $E$（共用边或角）：

   $$E = \{(u, v) : |x_u - x_v| \leq 1 \text{ and } |y_u - y_v| \leq 1\} $$
   • 判断相邻性（约束条件3）

2. 4-邻接图 $G$（只共用边）：

   $$G = \{(u, v) : |x_u - x_v| + |y_u - y_v| = 1\}$$
   • 判断路径可达性（约束条件4）

关键性质：

• 相邻性在8-邻接图上判断
• 连通性在4-邻接图上判断

---

观察 3：虚拟节点技巧

问题：如何高效判断某个位置能否到达边界？

解决方案：引入虚拟节点表示边界。

构造方法：

1. 对于每座摩天楼的8个相邻位置，如果没有其他摩天楼，创建虚拟节点（空格子）
2. 虚拟节点数量：$O(8n) = O(n)$
3. 选择最左下角的虚拟节点作为"边界代表"（节点0）
4. 所有与节点0在4-邻接图上连通的虚拟节点都"到达边界"

数学证明：

引理 1：最左下角的虚拟节点必定能到达边界。

证明：

• 设该节点坐标为 $(x_0, y_0)$
• 由于摩天楼数量有限且坐标有界，从 $(x_0, y_0)$ 向左或向下移动，最终必定到达 $|r| > 10^9$ 或 $|c| > 10^9$ 的边界
• 路径上都是空格子（没有摩天楼）

引理 2：与节点0连通的所有虚拟节点都能到达边界。

证明：

• 在4-邻接图上，连通性具有传递性
• 节点0能到达边界，连通的节点也能到达边界

---

1.3 割点判定

定义：在图论中，割点是指删除该点后，图的连通分量数增加的点。

本题的割点定义：拆除摩天楼 $u$ 后，某些空格子失去与边界的连接。

判定方法：

设摩天楼 $u$ 的8个相邻位置为 $N_8(u)$，其中：

• $V_0$：未建造的摩天楼（空格子）
• $V_1$：已建造的摩天楼和虚拟节点（空格子）

定理 2（割点判定准则）：

摩天楼 $u$ 是割点 $\Leftrightarrow$ 满足以下两个条件之一：

1. $|V_0| \geq 2$ 且 $V_0$ 中存在两个不连通的连通分量
2. $|V_1| \geq 2$ 且 $V_1$ 中存在两个在4-邻接图上连通的节点

证明：

条件1：$V_0$ 中有两个不连通的未建造摩天楼

• 拆除 $u$ 后，这两个摩天楼必须都能到达边界
• 但它们在8-邻接图上不连通（通过 $u$ 的相邻位置）
• 说明 $u$ 的位置对于连接它们是必需的
• 拆除 $u$ 会破坏连通性

条件2：$V_1$ 中有两个连通的已建造位置

• 这意味着在不经过 $u$ 的情况下，$V_1$ 内部已经连通
• 拆除 $u$ 后，$V_1$ 仍然连通，不会破坏到边界的路径
• 但如果 $V_1$ 中所有节点都不连通，则拆除 $u$ 可能破坏连通性
• 因此，只要 $V_1$ 内部有连通的，拆除 $u$ 就是安全的
• 取反：如果 $V_1$ 内部两两不连通，则 $u$ 可能是割点 ✗

实际代码中的判定逻辑：

• 如果 $|V_0| \leq 1$，不是割点（只有一个或没有未建造的相邻摩天楼）
• 否则，检查 $V_1$ 中是否有两个连通的节点
  • 有：不是割点
  • 无：是割点

---

二、算法设计：逆向贪心构造

2.1 算法总体框架

核心思想：

1. 逆向构造：从 $s_n$ 到 $s_1$
2. 贪心选择：每次选择合法的最大编号摩天楼
3. 动态维护：实时更新连通性和合法性

算法流程：

初始化：
    所有摩天楼未建造（vis[i] = false）
    虚拟节点已建造（vis[i] = true）
    初始化并查集维护空格子连通性
    
for i = n downto 1:
    选择编号最大的合法摩天楼 u
    ans[i] = u
    标记 u 为已建造（vis[u] = true）
    更新连通性
    更新所有受影响位置的合法性

复杂度分析：

• 时间复杂度：$O(n^2)$（每次选择 $O(n)$，共 $n$ 次）
• 空间复杂度：$O(n)$

---

三、代码模块详解

模块 1：数据结构与预处理

1.1 坐标哈希

const int V = 1e9;
struct Point {
    int x, y;
    Point() {}
    Point(int _x, int _y) : x(_x), y(_y) {}
    ULL hash() {
        return (ULL)(x + V) << 32 | (y + V);
    }
} a[MAXN];

功能：将二维坐标映射到一维哈希值。

数学原理：

• 坐标范围：$[-10^9, 10^9]$
• 偏移后：$[0, 2 \times 10^9]$
• 哈希公式：$h(x, y) = (x + V) \times 2^{32} + (y + V)$
• 保证不同坐标有不同哈希值（因为 $2 \times 10^9 < 2^{32}$）

时间复杂度：$O(1)$

---

1.2 并查集（Union-Find）

struct UFDS {
    int siz[MAXN], fa[MAXN];
    
    void init(int n) {
        std::iota(fa, fa + n + 1, 0);
        std::fill(siz, siz + n + 1, 1);
    }
    
    int find(int x) {
        while (x != fa[x])
            x = fa[x] = fa[fa[x]];  // 路径压缩
        return x;
    }
    
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (siz[x] < siz[y]) std::swap(x, y);
        fa[y] = x, siz[x] += siz[y];  // 按秩合并
    }
    
    bool tog(int x, int y) {
        return find(x) == find(y);
    }
} ufds;

功能：维护空格子的连通性。

优化：

• 路径压缩：find 操作均摊 $O(\alpha(n))$
• 按秩合并：保持树的平衡

应用：

• 判断两个空格子是否连通
• 判断某个空格子是否能到达边界（是否与节点0连通）

---

模块 2：初始化与建图

void init() {
    std::map<ULL, int> id;
    n = read(), Ttype = read();
    
    // 读入摩天楼坐标
    for (int i = 1; i <= n; i++) {
        a[i].x = read(), a[i].y = read();
        id[a[i].hash()] = i;
    }
    
    N = n;
    
    // 建立8-邻接图 e[] 和创建虚拟节点
    for (int i = 1; i <= N; i++)
        for (int o = 0; o < 8; o++) {
            Point p(a[i].x + dx[o], a[i].y + dy[o]);
            auto it = id.find(p.hash());
            
            if (it != id.end())
                e[i].push_back(it->se);  // 相邻的摩天楼
            else if (i <= n) {
                if (N >= 5 * n + 4)  // 虚拟节点数量过多
                    printf("NO\n"), exit(0);
                
                // 创建虚拟节点
                id[p.hash()] = ++N;
                a[N] = p;
                vis[N] = true;  // 虚拟节点初始为"已建造"（空格子）
                e[i].push_back(N);
            }
        }
    
    // 连通性检查
    if (!chk_connect())
        printf("NO\n"), exit(0);
    
    // 建立4-邻接图 g[]
    for (int i = 1; i <= N; i++)
        for (int o = 0; o < 4; o++) {
            Point p(a[i].x + dx[o], a[i].y + dy[o]);
            auto it = id.find(p.hash());
            if (it != id.end())
                g[i].push_back(it->se);
        }
    
    // 初始化并查集：合并所有相邻的虚拟节点
    ufds.init(N);
    for (int i = n + 1; i <= N; i++)
        for (int j : g[i])
            if (j > n)
                ufds.merge(i, j);
    
    // 找到最左下角的虚拟节点，作为边界代表（节点0）
    Point p = a[n + 1];
    for (int i = n + 1; i <= N; i++)
        if (a[i].x < p.x || (a[i].x == p.x && a[i].y < p.y))
            p = a[i];
    
    ufds.merge(0, id[p.hash()]);
    
    // 标记所有能到达边界的虚拟节点
    for (int i = n + 1; i <= N; i++)
        if (ufds.tog(i, 0))
            chked[i] = true;
}

算法步骤：

步骤1：读入数据，建立坐标到编号的映射

步骤2：建立8-邻接图并创建虚拟节点

• 对于每座摩天楼的8个相邻位置：
  • 如果有摩天楼：加入8-邻接图
  • 如果没有：创建虚拟节点（空格子）
• 虚拟节点编号：$n+1, n+2, \ldots, N$

步骤3：连通性检查

• 在8-邻接图上检查所有摩天楼是否连通
• 如果不连通，无解

步骤4：建立4-邻接图

• 只包含上下左右四方向的邻接关系
• 用于判断路径可达性

步骤5：初始化并查集

• 合并所有相邻的虚拟节点（在4-邻接图上）
• 建立虚拟节点的连通性

步骤6：选择边界代表

• 最左下角的虚拟节点必定能到达边界
• 将其与节点0合并

正确性证明：

引理 3：初始化后，与节点0连通的虚拟节点都能到达边界。

证明：

• 最左下角的虚拟节点 $(x_0, y_0)$ 能到达边界（引理1）
• 与它连通的虚拟节点也能到达边界（引理2）
• 并查集正确维护了连通性

---

模块 3：连通性检查

bool chk_connect() {
    static bool con_1[MAXN];
    static int q[MAXN], fr, ba;
    memset(con_1 + 1, false, n);
    q[fr = ba = 1] = 1, con_1[1] = true;
    
    while (fr <= ba) {
        int x = q[fr++];
        for (int y : e[x])
            if (!con_1[y] && y <= n)
                con_1[y] = true, q[++ba] = y;
    }
    
    for (int i = 1; i <= n; i++)
        if (!con_1[i])
            return false;
    
    return true;
}

功能：检查所有摩天楼在8-邻接图上是否连通。

算法：BFS遍历

时间复杂度：$O(n + m)$，其中 $m = O(n)$（每个节点最多8条边）

必要性：

• 如果摩天楼不连通，无法满足约束条件3
• 必须提前判断并输出 NO

---

模块 4：可达性判断

bool reachable(int id) {
    for (int y : g[id])
        if (vis[y] && ufds.tog(0, y))
            return true;
    return false;
}

功能：判断摩天楼 id 是否能到达边界。

算法逻辑：

1. 遍历 id 在4-邻接图上的所有邻居 y
2. 如果 y 是空格子（vis[y] = true）
3. 且 y 与边界连通（ufds.tog(0, y)）
4. 则 id 能到达边界

数学证明：

定理 3：摩天楼 $u$ 能到达边界 $\Leftrightarrow$ $u$ 的某个4-邻居是空格子且能到达边界。

证明：

• $\Rightarrow$：$u$ 能到达边界，必定通过某个相邻的空格子（路径的第一步）
• $\Leftarrow$：如果相邻的空格子能到达边界，$u$ 也能（路径 = $u$ + 空格子的路径）

时间复杂度：$O(1)$（最多4个邻居，并查集 find 均摊 $O(\alpha(n))$）

---

模块 5：割点判断

bool key[MAXN];

void mark(int x) {
    key[x] = false;
    
    if (vis[x]) {
        // x是空格子，通过4-邻接图传播
        for (int y : g[x])
            if (vis[y] && key[y])
                mark(y);
    } else {
        // x是摩天楼，通过8-邻接图传播
        for (int y : e[x])
            if (!vis[y] && key[y])
                mark(y);
    }
}

bool cut(int id) {
    // 步骤1：标记所有相邻位置
    for (int x : e[id])
        key[x] = true;
    
    assert(e[id].size() == 8);
    std::vector<int> ard[2];
    
    // 步骤2：分类相邻位置
    for (int x : e[id])
        if (key[x] && !vis[x])  // 未建造的摩天楼
            ard[0].push_back(x), mark(x);
    
    for (int x : g[id])
        if (key[x] && vis[x])   // 已建造的位置（空格子）
            ard[1].push_back(x), mark(x);
    
    // 步骤3：清理标记
    for (int x : e[id])
        key[x] = false;
    
    // 步骤4：判定
    if (ard[0].size() <= 1)
        return false;  // 未建造的相邻位置不超过1个，不是割点
    
    // 步骤5：检查已建造位置的连通性
    for (int i = 0; i < ard[1].size(); i++)
        for (int j = i + 1; j < ard[1].size(); j++)
            if (ufds.tog(ard[1][i], ard[1][j]))
                return true;  // 有两个连通的，不是割点
    
    return false;  // 所有已建造位置都不连通，是割点
}

功能：判断摩天楼 id 是否是割点。

算法步骤：

步骤1：标记所有8个相邻位置

步骤2：使用 mark 函数将相邻位置分成连通分量

• mark 函数通过DFS标记连通的节点
• 对于空格子：通过4-邻接图传播
• 对于摩天楼：通过8-邻接图传播
• 每次调用 mark 会标记一个连通分量

步骤3：分类相邻位置

• ard[0]：未建造的摩天楼
• ard[1]：已建造的位置（空格子）

步骤4：判定逻辑

• 如果 |ard[0]| ≤ 1，不是割点
• 否则，检查 ard[1] 中是否有两个连通的节点
  • 有：不是割点
  • 无：是割点

数学证明：

定理 4（割点判定正确性）：上述算法正确判定割点。

证明：

情况1：|ard[0]| ≤ 1

• 未建造的相邻位置不超过1个
• 拆除 id 后，不会出现两个不连通的未建造摩天楼
• 不是割点

情况2：|ard[0]| ≥ 2 且 ard[1] 中有两个连通的

• 拆除 id 后，ard[1] 仍然连通（通过4-邻接图）
• 未建造的摩天楼可以通过连通的空格子到达边界
• 不会破坏连通性，不是割点

情况3：|ard[0]| ≥ 2 且 ard[1] 中所有节点都不连通

• 拆除 id 后，ard[1] 的各个连通分量彼此隔离
• 某些未建造的摩天楼可能失去到边界的路径
• 可能破坏连通性，是割点

时间复杂度：$O(8)$（最多8个相邻位置）+ DFS标记 $O(n)$ = $O(n)$

---

模块 6：合法性检查

bool chk(int id) {
    assert(id <= n);
    
    if (vis[id])
        return false;  // 已经建造
    
    if (!reachable(id))
        return false;  // 无法到达边界
    
    if (cut(id))
        return false;  // 是割点
    
    return true;
}

功能：检查摩天楼 id 是否可以作为下一个建造的位置。

判定条件：

1. 未建造（!vis[id]）
2. 能到达边界（reachable(id)）
3. 不是割点（!cut(id)）

正确性：三个条件都是必要的，缺一不可。

---

模块 7：动态更新

void test(int id) {
    if (id > n) return;
    
    bool res = chk(id);
    
    if (vld[id] && !res)
        vld[id] = false, q.erase(id);  // 从合法集合中移除
    else if (!vld[id] && res)
        vld[id] = true, q.insert(id);   // 加入合法集合
}

void putin(int id) {
    for (int y : e[id])
        test(y);  // 测试所有8-邻居
}

void dfs(int x) {
    putin(x), chked[x] = true;
    
    for (int y : g[x])
        if (vis[y] && !chked[y])
            dfs(y);  // 遍历所有连通的空格子
}

void erase(int id) {
    vis[id] = true;  // 标记为已建造（空格子）
    
    // 更新并查集
    for (int x : g[id])
        if (vis[x])
            ufds.merge(id, x);
    
    // 更新所有受影响位置的合法性
    dfs(id);
}

功能：建造摩天楼 id 后，更新系统状态。

算法步骤：

步骤1：标记 id 为已建造

• vis[id] = true

步骤2：更新并查集

• 将 id 与所有相邻的空格子合并
• 维护空格子的连通性

步骤3：DFS更新受影响的位置

• 从 id 开始DFS遍历所有连通的空格子
• 对于每个空格子的8-邻居，重新检查合法性
• 更新合法集合 q

时间复杂度：$O(n)$（DFS遍历所有相关节点）

必要性：

• 建造一座摩天楼后，周围摩天楼的合法性可能改变
• 必须实时更新，保证贪心选择的正确性

---

模块 8：主算法

int main() {
    init();
    
    // 初始化合法集合
    for (int i = 1; i <= n; i++)
        if (vld[i] = chk(i))
            q.insert(i);
    
    // 逆向构造
    for (int i = n; i; i--) {
        auto it = --q.end();  // 选择最大的合法摩天楼
        ans[i] = *it;
        q.erase(it);
        erase(ans[i]);  // 建造并更新
    }
    
    printf("YES\n");
    for (int i = 1; i <= n; i++)
        write(ans[i]);
    
    return 0;
}

算法流程：

步骤1：初始化

• 调用 init() 建图
• 检查所有摩天楼的初始合法性
• 将合法的摩天楼加入集合 q

步骤2：逆向构造

• 从 $i = n$ 到 $i = 1$
• 每次选择 q 中编号最大的摩天楼
• 建造并更新系统状态

步骤3：输出答案

正确性证明：

定理 5（算法正确性）：上述算法构造的序列满足所有约束条件。

证明：

约束1（一次建一座）：显然满足

约束2（第一座无限制）：$s_1$ 可以是任意合法的摩天楼

约束3（相邻性）：

• 逆向看，拆除序列保证连通性
• 正向看，建造序列保证每座新建的与已建的在8-邻接图上连通

约束4（可达性）：

• 每次选择的摩天楼都通过 chk 检查
• reachable 保证能到达边界
• cut 保证不破坏连通性

字典序最大：

• 每次选择 q 中最大的元素
• 贪心策略保证 $(s_n, s_{n-1}, \ldots, s_1)$ 字典序最大

---

四、复杂度分析

4.1 时间复杂度

初始化：

• 读入数据：$O(n)$
• 建立8-邻接图：$O(8n) = O(n)$
• 建立4-邻接图：$O(4n) = O(n)$
• 连通性检查：$O(n)$
• 并查集初始化：$O(n \alpha(n))$
• 总计：$O(n)$

主循环：

• 外层循环：$n$ 次
• 每次操作：
  • 选择最大元素：$O(\log n)$（set 操作）
  • erase 更新：$O(n)$（DFS遍历）
  • chk 检查：$O(n)$（割点判断）
• 总计：$O(n^2)$

总时间复杂度：$O(n^2)$

对于 $n \leq 1.5 \times 10^5$，约 $2.25 \times 10^{10}$ 次操作，可能较慢但可以通过。

4.2 空间复杂度

数组空间：

• 坐标数组 a[]：$O(n)$
• 邻接表 e[], g[]：$O(8n + 4n) = O(n)$
• 并查集：$O(n)$
• 其他辅助数组：$O(n)$

虚拟节点：

• 每座摩天楼最多创建8个虚拟节点
• 总数：$O(8n) = O(n)$

总空间复杂度：$O(n)$

4.3 优化空间

可能的优化：

1. 启发式搜索：优先考虑度数大的节点
2. 增量更新：只更新真正受影响的节点
3. 缓存判定结果：避免重复计算

---

五、正确性证明总结

5.1 核心不变式

不变式1（连通性）：任何时刻，所有已建造的摩天楼在8-邻接图上连通。

不变式2（可达性）：任何时刻，所有已建造的摩天楼都能通过4-邻接图上的空格子路径到达边界。

不变式3（合法性）：集合 q 中的摩天楼都满足合法性条件。

5.2 算法终止性

定理 6（算法终止性）：算法必定终止且找到合法序列或判定无解。

证明：

• 初始化时检查连通性，不连通则判定无解
• 主循环每次从 q 中取出一个元素，最多 $n$ 次
• 如果某次 q 为空，说明无解（但题目保证有解则不会发生）
• 因此算法必定在 $O(n)$ 次迭代内终止

---

六、算法技巧总结

6.1 核心算法技巧

1. ✅ 逆向思维

   • 正向构造困难，逆向拆除简单
   • 拆除等价于建造的逆过程

2. ✅ 图的二元性

   • 8-邻接图判断相邻性
   • 4-邻接图判断可达性
   • 两种图协同工作

3. ✅ 虚拟节点技巧

   • 将"边界"具象化为虚拟节点
   • 简化可达性判断

4. ✅ 并查集维护连通性

   • 动态维护空格子的连通性
   • 高效判断是否到达边界

5. ✅ 割点判定

   • 通过相邻位置的连通性判断
   • 避免破坏整体连通性

6. ✅ 贪心策略

   • 每次选择最大的合法摩天楼
   • 保证字典序最大

7. ✅ 动态维护

   • 实时更新合法性
   • DFS传播影响

---

七、总结

7.1 算法精髓

本题采用的逆向贪心 + 图论的核心思想：

1. 问题转化：正向建造 → 逆向拆除
2. 图的建模：8-邻接图 + 4-邻接图
3. 虚拟节点：具象化边界，简化判断
4. 割点判定：保证连通性不被破坏
5. 贪心选择：每次选择最大的合法元素
6. 动态维护：实时更新受影响的节点