Exchange Arguments_杂项

Exchange Arguments

若相邻两项交换对总权值的影响无需用到两项之外的元素，则我们可以使用相邻交换贪心来处理这类问题。

在实际处理的时候若比较可以写为 $x<y\iff val(x)<val(y)$ 的形式那么比较一定正确，若仅仅只能写为 $f(x,y)<0$ 的形式则我们需要仔细考虑不等号的传递性以及等号的传递性。

譬如说 $f(x,y)$ 中含有一些 $\max/\min$，我们可以将 $\max(a,b)<c$ 拆为 $(a<c)\wedge (b<c)$ 来仔细观察条件，其他的情况同理。

如果排序关键字的条件不重不漏，或者在有交时给出的结果严格一致，那么这个 Exchange Arguments 极大可能可以用。

例题

经典的题是国王游戏，我们略过经典的题。

题

一棵树，每条边有权值，初始只有根，每次可以把连通块扩展一下，最小化所有点被扩展到的时间和。

考虑全局最小边，我们走到它的父亲必定第一步走它，所以我们直接合并这两个点，然后把其儿子接到父亲上，维护每个点的父亲可以用并查集，而找到新的全局最小边就需要用堆来实现了，比较两个元素就可以利用 Exchange Arguments。

B. [炼石计划–NOIP模拟十五]–T2–狗卡

游戏中有 $n$ 个武将，一开始并不会吸引人氪金，我们认为每个武将一开始都是 $0$ 级。

每个武将可以升级若干次，每升级一次，这个武将会每天会多吸引 $1$ 个人氪金。也就是说如果一个武将被升级过 $x$ 次，那么这个武将就会每天吸引 $x+1$ 个人氪金。

需要注意的是，一个人物必须按顺序升级，因为如果你先设计出神武将售卖，就没有人想买界武将了。

设计武将升级需要一定时间，第 $i$ 个武将升第 $j$ 次级需要 $a_{i,j}$ 天，狗卡同时只能设计一个武将。在一个武将从 $x$ 级升到 $x+1$ 级期间它仍然会每天吸引 $x$ 个人氪金。

它想知道当第 $m$ 天后游戏倒闭时最多能吸引多少人氪金。

由于狗卡正在蒸蒸日上，所以游戏会存在很长时间，保证 $m\ge10^{10}$。

类似的思路，全局最小值必定在升级完前驱后立刻被选，所以合并一下。

考虑每个武将如果每升一级代价都变大，那么直接每级作为一个独立的武将就可以了，所以我们维护一个栈，只要栈顶和次栈顶不满足这个相对关系就说明一定可以合并了。

比较同样只需要 Exchange Arguments，记录 $x$ 天升 $y$ 级即可。