题解：P14365 [JOISC 2018] 高速公路建设 / Construction of Highway

Emily1234 · 2025-11-15 09:49:42 · 题解

[JOISC 2018] 高速公路建设 / Construction of Highway 题解

(因为不喜欢打字所以费话也不多，开始)

求关

（洛谷！！！我辛辛苦苦打了三篇题解，为什么都没过！！！！！！！！！！！！！！！！！！！！！！）

问题核心分析

本题的关键在于理解道路建设的两个核心操作：

1. 成本计算：每次建设时，需统计从首都（城市 1）到城市 Aj的唯一最短路径上，所有 “前序城市活力值> 后序城市活力值” 的相邻城市对数量。

2. 活力值更新：计算成本后，将上述路径上所有城市的活力值统一更新为 Bj 的活力值。

由于每次建设的路径是 “从 1 到 Aj” 的唯一路径，且更新操作会覆盖整个路径的活力值，因此需要高效维护路径的 “逆序对数量” 和 “批量更新” 能力。

关键观察

1. 路径唯一性： 题目明确 “1 到Aj 的最短路径唯一”，结合建设规则（Aj 已连通 1，Bj 未连通），可知每次建设的路径是树的一条 “从根（1）到 Aj 的路径”（本质是构建一棵以 1 为根的生成树）。

2. 更新的幂等性： 若一条路径被多次更新，后续更新会覆盖之前的活力值。因此，路径上的活力值最终会变成最后一次更新时 Bj 的值，且同一路径段的活力值会趋于 “一致”。

3. 逆序对的简化： 当路径上的城市活力值全部相同时，逆序对数量为 0；若路径由多个 “活力值相同的连续段” 组成，则逆序对仅存在于相邻段的交界处（前一段活力值 > 后一段活力值时贡献 1）。

数据结构选择：并查集（DSU）优化

为高效处理 “路径查询逆序对” 和 “批量更新”，我们使用带标记的并查集，核心思想是将路径上 “活力值相同的连续城市” 合并为一个集合（称为 “块”），每个块维护：

• parent[x]：块的父节点（用于路径压缩）。
• value[x]：块的活力值。cnt[x]：块内城市的数量（仅根节点有效）。
• inv[x]：块内的逆序对数量（仅根节点有效，实际为块内相邻城市对的逆序贡献，因块内活力值相同，inv[x] = 0）。
• above_inv[x]：当前块与其父块之间的逆序贡献（若父块活力值 > 当前块活力值，贡献 1，否则 0）。

并查集核心操作

1. find 函数： 带路径压缩，找到城市 x 所在块的根节点，并维护路径上的逆序对总数（通过累加 above_inv）。

2. merge 函数： 将两个相邻块合并（当路径更新时，所有块的活力值变为 (B_j)，此时块间逆序贡献消失，可合并为一个大的块）。

算法步骤

1. 初始化： 每个城市初始为独立块，value[x] = C[x]，cnt[x] = 1，inv[x] = 0，above_inv[x] = 0（根节点无父块）。

2. 处理每次建设：

   a. 调用 find(A_j)，获取从Aj 到根（1）的路径上的总逆序对数量（即本次建设的成本），并输出。

   b. 再次遍历路径（通过 find 的路径压缩，路径已扁平化），将路径上所有块的活力值更新为 Bj 的活力值，并合并相邻块（此时块间逆序贡献为 0，可安全合并）。