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

pikiuk · 2025-07-21 15:14:13 · 题解

首先考虑 l_i+1=r_i 的部分分，相当于查询最小生成树路径上的最大边，也就是 l_i,r_i 在重构树上的 lca。

考虑全部数据，相当于找出重构树上 r_i-l_i+1 个叶子节点点点权前 r_i-l_i 大的两两 lca，注意到重构树上每个点代表一次合并，因此 k 个叶子点恰有 k-1 个 lca，从而问题变为求解编号在 [l_i,r_i] 内点的两两 lca 点权和。

此时我们考察重构树某个点何时会被贡献到答案里，注意到每个点 u 有且仅有两个儿子，不妨记作 s_1,s_2，该点会被贡献到答案当且仅当 s1,s2 的子树内均存在编号在区间 [l_i,r_i] 的点。

也就是说，若存在 x\in \texttt{subtree}(s_1),y\in \texttt{subtree}(s_2)(x<y)，所有包含 [x,y] 的询问都会获得 w_u 的贡献，其中 w_u 是 u 的点权（注意该贡献不能累加，所以对于每个节点要将贡献范围去并）。

仿照铃原露露的手法即可求出支配点对，扫描线配合树状数组完成后续工作即可。没有做过铃原露露的同学可以继续阅读。

考虑画出 l-r 平面（横轴为 l，纵轴为 r），平面上一个点代表一次询问，那么一个 (x,y) 的贡献区间相当于左上的 2-side 矩形。由于贡献是覆盖的，因此若当 x 固定时，y 只需考虑尽可能小的那个即可，因此考虑启发式合并维护子树叶子节点编号，合并时将被合并点与其对应的前驱后继凑成 (x,y,w_u) 的贡献对，扫描线处理，贡献对的数量和启发式合并的复杂度是同阶的。

另外注意由于对于每个点 u，其贡献是不能叠加的，所以对 l 从 n 到 1 更新时，还需额外记录每个 u 的最小 r 值，用树状数组实现单点修改，区间查询即可。

综合时间复杂度 \mathcal{O}(m\log m+n\log^2 n+q\log n)。

代码很好写，如果实在需要私信找我要。