支配对
stripe_python
·
·
算法·理论
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},我们将最小值和非最小值分开维护:
- 最小值:V_1=\begin{bmatrix} \text{mn} \times \text{cnt} \\ \sum\limits_{a_i =\text{mn}} h_i \\ \text{cnt} \end{bmatrix}。
- 非最小值:V_2=\begin{bmatrix} \sum \limits_{a_i > \text{mn}} a_i \\ \sum\limits_{a_i >\text{mn}} h_i \\ \text{len}-\text{cnt}\end{bmatrix}。
区间 +\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 下传进行讨论:
- 若 v 的最小值等于 u 打标记前的最小值,则 M_1(v) 复合 M_1(u),M_2(v) 复合 M_2(u)。
- 若 v 的最小值大于 u 打标记前的最小值,则 M_1(v),M_2(v) 均复合 M_2(u)。
这样我们得到了 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:
- 若 a_k \ge a_j,则 |a_i-a_k| \ge |a_i-a_j|,点对 (i,j) 支配 (i,k)。
- 若 a_k<a_i,列出 (i,k) 不被 (j,k) 支配的条件为 |a_i-a_k| < |a_j-a_k|,去掉绝对值得到 a_k-a_i < a_j-a_k,移项得 a_k-a_i<\dfrac{a_j-a_i}{2}。
根据推导,每向右寻找一次支配对 (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) 种。这叫做第二类支配点对。
两种常见的支配对形态:
- 对每个 i,可以求出 O(\log n) 个 j,这些 (i,j) 支配了 (i,1) \sim (i,n) 的贡献。
- 对信息维二区间合并分治,则 O(n) 对跨越中线的贡献支配了两侧 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)。代码。
:::::