题解：P10327 [UESTCPC 2024] 汉诺塔排序问题

· · 题解

这也太难了！！！！！！

本题解参考了 GD 省集的官方题解，但是官方题解过于晦涩难懂了，这是一个（可能）说人话的版本。

下文中的 A 序列即题面中的 p。

考虑将整个过程倒过来：一开始，B 柱上有（从上到下）1 \sim n 的圆盘，我们要将其按照指定顺序挪到 A 上。

不难发现，如果 A 底部的圆盘归位了，我们之后一定不会再移动它，因为它并不会影响之后所有圆盘。因此，我们一定自底向上将 A 排好，这是不劣的。

定义 pos_x 表示 \ge x 且未归位的元素个数。 定义 pre_x 表示 x 在未归位圆盘中的（大小）前驱，nxt_x 表示其在未归位圆盘中的后继。

不妨假设我们要将 B 中的某个圆盘挪到 A 顶部。手玩可以发现，最优操作一定形如将 B 和 C 顶部的若干圆盘先归并到 A，再全部挪到 C（特别的，这些圆盘中最大的一个可以直接挪到 C，从而节省一次操作）。这时我们要的圆盘已经在 B 顶部了，我们将其直接挪到 A。（从 C 中取圆盘的流程同理。）

我们称一次这样的操作为基本操作。对于一次挪动了 k 个额外圆盘（即操作结束后没有放置在 A 上的圆盘）的基本操作，其额外代价（即挪动额外圆盘所需代价）为 2k-1。总代价即为所有基本操作的额外代价之和加上 n。定义一次基本操作的“下界”为 pos_{lst}-1，其中 lst 表示该次基本操作移动的额外圆盘中最大的一个。

下图是一次基本操作的示例。

考虑如何快速维护移动过程中的状态。观察到，一次基本操作对 B,C 归并后形成的序列，影响只有删除这个序列中一个元素。此外，基本操作相当于“推平”了这个序列的一个前缀，将这个前缀中的所有元素依次放在某个栈顶部。

因此，我们可以尝试使用一个“虚栈” st 实时维护“实栈” B,C 归并后形成序列中的非平凡元素。具体来说，如果一个元素 x 不在 st 中，我们认为他和 pre_x 在同一个“实栈”中——显然，x 在“实栈”中位于 pre_x 的正下方。虚栈初始为空。

假设 A_i = p。于是，我们可以一直弹出“虚栈”中的元素，直到虚栈栈顶元素 x 满足 pos_x \le pos_p。假设弹出的元素中与 p 位于同一“实栈”的最大的元素是 y，那么这轮操作的额外代价是 2((n - i + 1) - y + 1) - 1……吗？

考虑如下 Hack：

A=\{3,5,2,1,4\}

考虑前两步，如果每轮都只操作“必须操作的位置”（即图 1），那么第二轮需要重新挪动 1,2 两个圆盘，最终比第一步操作到圆盘 4（图 2）多一次操作。

因此，我们不仅有可能新进行一次基本操作，还有可能“拓展”之前进行的基本操作。

我们不妨先不管这一点，观察基本操作对虚栈造成的影响。注意到，留在栈中的元素，其 pos 是不会改变的，因此可以直接维护；每次弹栈结束后，p 下方的元素状态会改变，可能造成一次入栈。

也就是说，我们至少需要给虚栈中元素两个属性：pos 和 diff，后者表示该元素和 pre_x 是否在同一个实栈中。

现在考虑可能拓展已有操作的情形，我们还要额外维护一个属性 tag，定义为可以拓展到该元素的基本操作的最小下界。

弹栈时维护一个变量 tag'，表示目前可以拓展到栈顶的基本操作的最小下界。同时维护这一轮操作的最小额外代价 cur。

不难发现，假设要拓展已有操作将栈顶元素上方（不含栈顶）元素清空，就相当于让 cur 加上 2(tag'-pos)。

对于栈顶元素 pos > pos_p 的情形：

先令 tag' \gets \min\{tag', tag\}。

处理结束后，弹出栈顶。

弹栈结束后，考虑栈顶元素。

最后，由于基本操作将所有额外圆盘归并到了与 p 不同的实栈上，考虑目前的栈顶元素：

不难验证其正确性。

综上，我们解决了本题，时间复杂度 O(n \log n)，瓶颈在使用树状数组求 pos_p。代码比较好写。