支配对

· · 算法·理论

P7880 [Ynoi2006] rldcot

给定一棵 n 个节点的有根树,根节点为 1,边有边权。

进行 q 次询问,给定 l,r,查询对 [i,j] \subseteq [l,r],有多少不同的 \text{dep}_{\text{lca}(i,j)}。

::::::success[题解]

转 l-r 二维平面分析,枚举 (i,j) 并将该坐标处的颜色设为 \text{dep}_{\text{lca}(i,j)},则询问是 2-side 矩形数颜色。

取固定的 l,对于颜色 u,若它在 x \ge l 的区域存在多个点,则只需保留 y 坐标最低的点以落入 y \le r 的询问区域。

对 x 轴降序扫描线,维护 f_u 为 x \ge l 且颜色 =u 的点的 y_{\min}。询问是求 f_u \le r 的 u 的数目,以 f 为下标开树状数组即可。

注意到 (i,j) 有 O(n^2) 对,复杂度不可接受。事实上,我们可以只保留一部分点对。

考虑 [l_1,r_1] \subseteq [l_2,r_2] 且 \text{lca}(l_1,r_1)=\text{lca}(l_2,r_2)=x 的点对 (l_1,r_1) 和 (l_2,r_2),可以发现 (l_2,r_2) 是无用的。因为 (l_1,r_1) 可以支配 (l_2,r_2),也即统计 (l_2,r_2) 时一定统计了 (l_1,r_1),则 (l_2,r_2) 对颜色数没有贡献。

我们只要保留不被支配的这些点对,这属于第一类支配对。

考虑在 x 处统计 \text{lca}(i,j)=x 的 (i,j)。由于支配关系是极短的,我们只要对每个 i 找到最小 / 最大的 j 满足 \text{lca}(i,j)=x,则 (i,j) 必为支配对。

我们用一个 std::set 维护子树内所有点的标号构成的集合,在 x 处继承重儿子,暴力枚举轻子树每个点,查出前驱后继后更新支配对,在枚举结束后合并 set。

根据树上启发式合并的理论,上述算法求支配对的复杂度为 O(n \log^2 n),且支配对的数目为 O(n \log n)。

::::info[树上启发式合并]

树上启发式合并,俗称 dsu on tree,是构造子树不删除莫队的方法。

考虑下面的 DFS 流程:先 DFS 轻子树,计算出轻子树的答案后清空数据结构,再 DFS 重子树,并将重儿子处的结构保留。

由于轻子树大小之和是 1log 的,上述算法的复杂度即为 O(n \log n)。本质是树上静态轻重链分治。

::::

我们只要保留这 O(n \log n) 个支配对,此时再进行 2-side 矩形数颜色即可。复杂度 O(n \log^2 n+q\log n)。代码。

:::::info[第一类支配对]

本题的模型可以抽象为,两两对象产生 O(n^2) 对贡献,但是本质不同的贡献只有 O(n) 种。只要保留贡献本质不同的若干点对,这叫做第一类支配点对。

本题是第一类支配对在树上的应用,考虑 [u,v] \subseteq [l,r] 产生贡献 \text{lca}(u,v),由于 LCA 只有 n 个,故我们保留 u 在子树中的前驱后继即可。

:::::

::::::

P13342 [EGOI 2025] Wind Turbines / 风力涡轮机

给定一张 n 个点 m 条边的无向带权图。进行 q 次询问,给定 l,r,你需要选择一些边,使得每个点都可以仅通过选择的边到达 [l,r] 中的点,最小化边权和并输出。

:::::success[题解]

询问可以描述为,建立虚点 S 并连边 \forall i \in [l,r],S \leftrightarrow i,边权为 0,求新图上 MST 边权和。

考虑 r-l=1 的情形,此时 l \to r 的瓶颈边会被删去,建 Kruskal 重构树后求 LCA 点权即可。

将上述观察扩展到一般情况。记 k=r-l+1,则对于 [l,r],其两两路径上的瓶颈边需要被删去。在 Kruskal 重构树上,这 k 个节点恰有 k-1 个本质不同的 LCA,故问题转化为求区间不同 LCA 点权和。

树上启发式合并求出 O(n \log n) 个第一类支配对 (u,v),询问转化为 2-side 矩形数颜色,每个颜色的贡献是该颜色的权值。对 x 轴降序扫描线,对每个颜色只保留 y 最小的位置,只要树状数组维护前缀和。

复杂度 O(m \log m+n\log^2 n+q\log n)。代码。

:::::

P8528 [Ynoi2003] 铃原露露

给定一棵 n 个节点的有根树,根节点为 1,同时给定长为 n 的排列 a_i。

进行 q 次询问,给定 l,r,查询有多少 [L,R] \subseteq [l,r] 满足 \forall a_x,a_y \in [L,R], a_{\text{lca}(x,y)} \in [L,R]。

:::::success[题解]

容易树上启发式合并求出 O(n \log n) 个第一类支配对,只需注意前驱后继是在 a_i 中求得的。

考察支配对 (x,y,z),其中 a_x \le a_y 且 z=\text{lca}(x,y),则需要 \forall [a_x,a_y] \subseteq [L,R], a_z \in [L,R]。故 (x,y,z) 会否定掉 [a_x,a_y] \subseteq [L,R] \land a_z \notin [L,R] 的区间。

转 l-r 二维平面分析,则支配对的否定范围是两个 3-side 矩形加法,询问是求 2-side 矩形中点权为 0 的整点数。

将修改差分后对一维扫描线,用数据结构维护另一维,可以发现这是一个扫描线历史和问题,数据结构需要支持区间加,区间求历史 0 个数,保证非负。

记 i 处的历史信息为 h_i。设线段树节点 [l,r] 内的最小值为 \text{mn},其出现次数为 \text{cnt},我们将最小值和非最小值分开维护:

区间 +\delta 的矩阵为 \begin{bmatrix}1 &0& \delta \\0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}。更新历史信息时,若根节点 \text{mn}=0,则对根节点的 V_1 左乘 \begin{bmatrix}1 &0& 0\\0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix},否则忽略操作。可以发现,标记矩阵也需要分最小值和非最小值维护 M_1 和 M_2。

考虑 pushdown 的实现。注意到区间内元素的相对大小不变。设父节点 u,子节点 v,类似 SegBeats 下传进行讨论:

这样我们得到了 O(3^3 q\log n) 的做法。进行半群优化,只维护形如 \begin{bmatrix}1 &0& A\\0 & 1 & B \\ 0 & 0 & 1\end{bmatrix} 的标记即可,且 M_1,M_2 的 A 标记总相同,只需要存一个。

最终复杂度 O(n \log^2 n+ q\log n)。代码。

:::::

CF765F Souvenirs

给定长为 n 的序列 a_i。进行 q 次询问,给定 l,r,查询

\min_{i,j \in [l,r], i\ne j} |a_i-a_j|

::::::success[题解]

钦定 i<j。转 l-r 二维平面分析,将坐标 (i,j) 的权值定义为 |a_i-a_j|,则查询是 2-side 矩形求 \min,我们需要减少点对数,这属于第二类支配对。

不妨设 a_j \ge a_i,对于 a_j<a_i 的情形同理。

取固定的 i 向右扫描,则 j >i \land a_j \ge a_i 的最小的 j 形成的 (i,j) 必然是支配对。考虑下一个位置 k 满足 i<j<k 且 a_i \le a_j:

根据推导,每向右寻找一次支配对 (i,k),差值至少折半,故 k 只会有 O(\log V) 个,支配对的总数为 O(n \log V)。

我们倒序扫描 i=n \to 1,使用权值线段树维护值域区间内的最小下标。对当前位置 i,设值域上界 R=+\infty,我们在线段树 [a_i,R] 上查询最小的 j,则 (i,j) 为支配对。令 R \gets a_i +\lfloor \frac{a_j-a_i-1}{2}\rfloor 重复上述过程,直到 j 不存在结束这个过程,内层循环至多 O(\log V) 轮。

求出所有支配对后,问题转为静态 2-side 矩形数点,扫描线配合树状数组即可。

复杂度 O(n \log n \log V+q\log n)。代码。

:::::info[第二类支配对]

本题的模型可以抽象为,两两对象产生 O(n^2) 对贡献,本质不同的贡献有 O(n^2) 种。这叫做第二类支配点对。

两种常见的支配对形态:

本题属于 O(\log n) 个 j 这类模型。

:::::

::::::

P9678 [ICPC 2022 Jinan R] Tree Distance

给定一棵 n 个节点的无根树,边有边权。进行 q 次询问,给定 l,r,查询 \min \limits_{l\le i < j \le r} \text{dis}(i,j)。

:::::success[题解]

转 l-r 二维平面分析,将点对 (i,j) 的权值视作 \text{dis}(i,j),询问是 2-side 矩形求 \min,但点对数量不可接受。

根据第二类支配对的理论,考虑对信息维分治。直接拆开 \text{dis} 会涉及 LCA 深度,这启发我们任意定根后,用点分治的方法枚举 LCA 为 x,钦定 \text{lca}(i,j)=x 后在 x 子树内求支配对。

记 \text{dis}(u,x)=f_u。考察三点 i<j<k,则 (i,k) 被 (i,j) 支配的条件为 f_j \le f_k。取固定的 k,求出点集 S=\{u \mid f_u \le f_k\},则 k 与它在 S 中的前驱后继形成了支配对。

我们将子树按 f 升序排序并扫描,用一个 std::set 维护已扫描点的标号,扫到 u 时查询其前驱后继作为支配对即可。

最后的问题是 2-side 矩形数点,扫描线树状数组即可。复杂度 O(n \log^2 n+q \log n)。代码。

:::::