专栏文章

题解：P13342 [EGOI 2025] 风力涡轮机

cchen_zheAya
P13342题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miosw5ra
此快照首次捕获于
2025/12/03 00:36
3 个月前
此快照最后确认于
2025/12/03 00:36
3 个月前
查看原文
这是 官方题解 的 AI 翻译。

EGOI 2025 官方题解 - Wind Turbines (风力发电机)

任务作者：Chur Zhe Yaw, Shi Wei Tia
2025 年 7 月 16 日

引言

在这个问题中，我们给定一个无向带权图，需要回答一些查询，每个查询询问将图中每个节点连接到区间 [li,ri][l_i, r_i] 内任意一个节点的最小代价。

子任务 1: M=N−1M = N - 1 且 vi=ui+1v_i = u_i + 1

在这个子任务中，图是一条路径。对于一个查询 [li,ri][l_i, r_i]，最优解是添加所有边 (0,1),(1,2),…,(li−1,li)(0, 1), (1, 2), \dots, (l_i-1, l_i) 和 (ri,ri+1),…,(N−2,N−1)(r_i, r_{i+1}), \dots, (N-2, N-1)。为了高效地为每个查询计算这个代价，我们可以使用前缀和进行预计算。运行时间是 O(N+Q)O(N + Q)。

子任务 2: N,M,Q≤2,000N, M, Q \le 2,000 且 ∑(ri−li+1)≤2,000\sum(r_i - l_i + 1) \le 2,000

在这个子任务中，约束足够小，可以为每个查询运行一个最小生成树 (MST) 算法，如 Kruskal 或 Prim。为了处理一些节点免费连接到岸边这一事实，我们需要在运行 MST 算法之前，添加一条连接 [li,ri][l_i, r_i] 中所有节点的、边权为 0 的路径。这个解法的时间复杂度是 O(Q⋅Mlog⁡M+∑(ri−li+1))O(Q \cdot M \log M + \sum(r_i - l_i + 1))。

子任务 3: ri=li+1r_i = l_i + 1

在这个子任务中，每个查询都恰好有两个节点连接到岸边。这意味着，与求整个图的 MST 相比，每个查询都可以省去一条边的代价。应该被移除的边是路径上从 lil_i 到 rir_i 的最重的那条边。为了高效地为每个查询找到这条边，我们可以使用倍增 (binary lifting)：
首先，任意选择一个根，将图变为树。然后对于每个节点 vv 和每个 2 的幂次 pp，计算从节点 vv 向上走 pp 步的路径上遇到的最重边的权重。同时，也记录下从 vv 向上走 pp 步后到达的节点。这两个值都可以用动态规划在 O(Nlog⁡N)O(N \log N) 的时间内计算出来。
然后，为了回答一个查询 (li,ri)(l_i, r_i)，我们可以计算从 lil_i 到最低公共祖先 (LCA) 以及从 rir_i 到 LCA 的路径上的最重边：我们可以像标准的倍增 LCA 算法那样“向上走”到 LCA，并取沿途找到的最重边的最大值。运行时间是 O(Nlog⁡N+Qlog⁡N)O(N \log N + Q \log N)。

子任务 4: 1<ci≤21 < c_i \le 2

这个子任务可以用与 100 分解法（见下文）类似的观察来解决，但有显著的简化。特别地，根据区间 [l,r][l, r] 的大小，我们知道总共需要支付多少条连接的费用。因此，我们只需要找出需要使用多少条代价为 2 的连接。这也可以通过计算在每个查询中，只由 c=1c=1 的边组成的图中有多少个连通分量来得出。

子任务 5: ∑(ri−li+1)≤400,000\sum(r_i - l_i + 1) \le 400,000

假设 qi=[li,ri]q_i = [l_i, r_i] 是一个查询。这个查询的代价是原始图的 MST 代价减去某些边的代价。具体来说，那些在 MST 中连接了两个集合，而这两个集合都包含来自 [li,ri][l_i, r_i] 的风力发电机的边，正是我们在 MST 中不需要支付费用的边。为了解决这个查询，我们只需要找到这些边的代价之和。
我们使用 Kruskal 算法来构造输入图的 MST。我们可以稍微扩展 Kruskal 算法中使用的并查集数据结构来计算 MST。在此之前，我们读入所有查询，并在每个节点上存储一个它所属的查询列表。由于 ∑(ri−li+1)≤400,000\sum(r_i - l_i + 1) \le 400,000，我们不会存储太多的值。当合并两个集合时，我们也可以合并它们的查询索引列表，并存储在合并后的集合中。我们通过遍历较小集合中存储的所有查询索引来做到这一点，并：(1) 检查它们是否也存储在较大的集合中（如果是，我们可以记录此信息并更新该查询的成本节省），以及 (2) 将它们添加到较大集合的列表中。总的来说，这需要 O(Nlog⁡N)O(N \log N) 的时间，因为每当一个顶点作为较小集合的一部分被处理时，它在联合操作后将属于一个至少是原来两倍大的集合。
替代解法：也可以使用虚树 (Virtual Trees) 在 O((ri−li+1)log⁡n)O((r_i - l_i + 1) \log n) 的时间内处理每个查询 (参见例如 https://codeforces.com/blog/entry/140066)。

子任务 6: li=0l_i = 0

有多种方法可以完成这个子任务：
  • 采用一个 100 分解法（见下文）的简化版本，其中可以跳过树状数组，因为所有查询都从 l=0l=0 开始。
  • 解决离线动态 MST 问题，即每次添加一条从 ii 到 i+1i+1 的权值为 0 的边。关于如何解决离线动态 MST 问题，可以参见例如 https://codeforces.com/blog/entry/105192。
  • 使用树链剖分 (Heavy Light Decomposition)，可以通过找出在 MST 中哪条边不再需要使用并移除它，来计算查询 [0,r][0, r] 和查询 [0,r+1][0, r+1] 之间的变化。
我们把细节留给读者去探索 :)

完整解法

要获得此问题的满分，我们需要一些思路和数据结构。
预处理：让我们在处理任何查询之前，先对输入图运行 Kruskal 的 MST 算法。在这样做的时候，我们可以构建一棵包含 2n−12n-1 个节点的 Kruskal 树，其中包括：
  • nn 个叶节点，每个代表一个城市。
  • n−1n-1 个内部节点，每个代表原始 MST 中使用的一条电缆。
构建这棵树的步骤如下：
  1. 按成本非递减的顺序对所有电缆进行排序。
  2. 按顺序处理每条电缆：
    • 如果 uiu_i 和 viv_i 已经连接，跳过这条电缆。
    • 否则，创建一个新的内部节点 yy 并使其成为 uiu_i 和 viv_i 所在树的根的父节点。
    • 然后，将 uiu_i 和 viv_i 所在树的根更新为 yy。
可以观察到，任何不在原始 MST 中的电缆在任何情况下都不会被建造；因此我们可以安全地忽略这些电缆。 现在，让 yiy_i 是树中对应于电缆 ii 的节点。它当且仅当 yiy_i 至少有一个直接子节点，且该子节点的子树中所有叶子节点都没有发电厂时，才会被建造。换句话说，电缆 ii 不被建造，当且仅当 yiy_i 的两个直接子节点在它们各自的子树中都至少有一个发电厂。
我们还将预处理这棵 Kruskal 树，以便我们可以在 O(log⁡n)O(\log n) 或 O(1)O(1) 的时间内回答 LCA 查询。
处理查询：我们按 rir_i 的递增顺序处理查询（扫描线）。如果 Kruskal 树中的一个（叶）节点的索引小于我们当前正在处理的 rir_i，我们就称它为激活 (active) 的。
考虑 Kruskal 树中的一个内部节点 uu，让 kuk_u 是以 uu 为根的子树中任何激活叶子的最大索引（这最多是 rir_i）。另外，假设 aa 和 bb 是 uu 的直接子节点。那么，对应于 uu 的电缆不被建造，当且仅当 ka≥lik_a \ge l_i 和 kb≥lik_b \ge l_i。确实，这仅在以 aa 为根的子树和以 bb 为根的子树都包含在 [li,ri][l_i, r_i] 范围内的风力发电机时发生。
我们现在注意到：
ku=max⁡(ku.a,ku.b)k_u = \max(k_{u.a}, k_{u.b})
因此，我们需要高效地计算满足上述条件的电缆的 cc 值之和。关键的观察是，这个和等于以下各项的和：
  • 所有满足 ku≥lik_u \ge l_i 的 uu 的 wu.par−wuw_{u.par} - w_u 之和。
在这里，uu 可以是一个内部节点或一个叶节点。u.paru.par 表示节点 uu 的父节点（如果节点 uu 没有父节点，定义 wu.par=0w_{u.par} = 0）。如果 uu 是一个内部节点，wuw_u 是对应于 uu 的电缆的成本。如果 uu 是一个叶节点，定义 wu=0w_u = 0。
为此，我们将维护一个以 kuk_u 为索引的树状数组（或线段树）来高效地计算这个和。具体来说，对于每个 ll，我们将维护所有满足 ku≥lk_u \ge l 的 uu 的 wu.par−wuw_{u.par} - w_u 之和。
我们可以在执行扫描线的同时有效地维护 kuk_u 的值。当激活一个叶子 xx 时，从该叶子到根的所有节点的 kk 值都将被设置为新激活叶子的索引。沿着这条从叶到根的路径，有几个共享相同 kk 值的“链 (chains)”。
我们将一条链定义为从某个内部节点 uu 到叶子 kuk_u 的最长路径。我们称这条链上最顶端的顶点为链的根。
当激活一个叶节点 xx 时（当前最大的激活节点），这将创建一条从树根一直到 xx 的新链，并覆盖这条路径上的任何先前存在的链，使它们变短。
我们可以观察到，在对 rr 的扫描线过程中，链改变根的总次数是 O(Nlog⁡N)O(N \log N)。这是因为，在具有两个大小为 s1s_1 和 s2s_2 的子树的节点 uu 处，穿过 uu 的链最多可以改变方向 min⁡(s1,s2)\min(s_1, s_2) 次。最坏的情况是在一个平衡二叉树中，根处的链改变方向 N/2N/2 次；根下一层的节点处的链改变方向 N/4N/4 次，依此类推。
根据上述观察，我们可以逐一处理每个链根的变化（总共 O(Nlog⁡N)O(N \log N) 次），并且每次发生变化时，在 O(log⁡N)O(\log N) 的时间内更新树状数组中受影响的索引。
这些链可以通过简单地存储所有链根的 kuk_u 值来维护，然后在激活后使用 LCA 查询向下遍历新的根到叶路径。确实，假设我们激活了节点 xx，那么我们可以通过查询 xx 和 kuk_u 的 LCA 来找到根到 xx 路径与从 uu 开始的链的交集上的最后一个重叠顶点。（或者，树链剖分或其他树数据结构可以帮助遍历这些路径）。然后我们可以继续到这个 LCA 的一个子节点，处理下一条链，同时更新树状数组和链根。
时间复杂度：排序边需要 O(Mlog⁡M)O(M \log M)，树状数组查询需要 O(Qlog⁡N)O(Q \log N)，激活叶子并更新树状数组需要 O(Nlog⁡2N)O(N \log^2 N)。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...