Exchange-Argument小总结

Exchange-Argument

• 参考资料：2022 集训队论文《浅谈一类基于交换的贪心在信息学竞赛中的应用》

• 本文主要介绍树上形式。

一般形式

你需要为 \(n\) 个元素安排一个排名，得到一个序列 \(a\)，最小化某函数 \(F(a)\)。

如果存在一个满足传递性和强完全性的关系 \(\le\)，满足 \(a,b\) 均为元素， $ ab,F(s_1+a+b+s_2)F(s_1+b+a+s_2)$，则按照 \(\le\) 排序后的排名可以最小化 \(F(a)\)。

典例为 NOIP2012 国王游戏。

我们在这里略去证明，详见参考资料。

• 强完全性指 \(\forall a,b, a\le b\bigvee b\le a\)，显然满足强完全性一定满足自反性。
• 条件中 \(\{s_1+a+b+s_2\}\) 为全集。

树上问题

例题

给定一棵树，需要为树的每个节点安排排名 \(p_u\)，父节点的排名需要低于子节点。每个点有一个价值 \(c_i\)，需要最小化 \(\sum c_u\times p_u\)。

分析与结论

唯一的变化是，对于原问题元素的比较 \(\le\)，拓展到了对于子序列的比较，即 \(a,b\) 为原来元素的一个序列。

以下是一个重要结论

考虑一个元素 \(v\)，我们希望说明如果它的父亲 \(u\)， \(u>v\)，那么 \(v\) 一定在 \(u\) 之后立刻被选择，此时将 \(v,u\) 合并，可以得到一个规模为 \(n-1\) 的子问题。

考虑证明 \(u\) 被选择后一定会选择 \(v\)，对于一个满足树的限制的排列 \(p\)，如果 \(u,v\) 不相邻，那么由于 \(v>u\)，所以对于序列 \(p_1,p_2\dots u,p_l,p_{l1} \dots p_r,v,\dots,p_n\)，一定有 \(u>p_{l,r} \bigvee p_{l,r}>v\)，否则 \(v<u\)，如果为前者，那么交换 \(u\) 和 \(p_{l,r}\)，后者同理，所以 \(v\) 一定紧接着 \(u\) 被选择。

我们可以用以下两种方式解决问题。

方式1

考虑最大的元素 \(v\)，显然可以合并它和它的父亲 \(u\)，变成一个新的规模更小的问题。

合并的过程可以用并查集维护连通块，注意区分并查集父亲和实际父亲。

使用 priority_queue 或者 set 可以实现加入删除和查询最小值，priority_queue 的方式是同时维护一个代表删除的 priority_queue，实际上 priority_queue 会比 set 快 \(1\) 倍。

注意实现的时候，如果找到了根，那么根其实有可能不在 priority_queue 里面，可删除的 priority_queue 如果删除了不存在的元素是会出问题的，所以一定要特判掉。

复杂度 \(O(n\log n)\)

方式2

我们考虑对每个子树求其答案。

利用分析中的结论，不妨将一棵子树划分成一些必须连续选择的序列，作为树对排列顺序的要求，将这些连续的序列视为一个元素后，我们可以对序列按照正常方式排序得到最优解。

划分序列的过程是对于一棵子树 \(u\)，将它的所有儿子的序列拿来排序，尝试将 \(u\) 与最小的序列合并得到新的序列，如果 \(u\) 当前所在的序列较大，由于结论我们知道合并后一定能拿到最优解，否则停止合并，此时 \(u\) 所在序列的权值最小，一定会被最先选择，其中 \(u\) 又一定会被第一个选择。

容易发现合并的过程一定不会改变子树内的选择顺序。

合并时采用启发式合并，利用 set 或 priority_queue 维护当前子树序列，复杂度为 \(O(n\log^2n)\)，但优势在于可以求出所有子树的答案。

当然可以使用可并堆达到 \(O(n\log n)\)

注意到其实一遍 dfs 就可以解决问题，因为启发式合并复杂度保证的来源是合并一次的复杂度为 \(O(\min(|u|,|v|))\)，所以并不需要提前计算子树大小，直接合并即可，set 或 priority_queue 的 swap 操作是 \(O(1)\) 的。

碎碎念

Exc-Arg 除了直接解决问题外，也可以用来简化问题，将选择元素并重排的问题变为排序后选择子序列的问题。

对于树上的情况，我还没有见到过相关的问题。