自动搬运

查看原文

来自洛谷，原作者为

	Moeebius µ || blog.moeebius.top || 是微渺/的希望/我们依然前行

搬运于2025-08-24 22:56:57，当前版本为作者最后更新于2025-04-09 11:50:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这也太难了！！！！！！

本题解参考了 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：

考虑前两步，如果每轮都只操作“必须操作的位置”（即图 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\}$。

• 如果其 $diff = \text{true}$，则意味着其前驱必须成为额外圆盘。此时，拓展已有操作的代价是 $cur+2(tag'-pos)$，将这轮的额外操作设为到 $nxt(pos)$ 为止的代价是 $\max\{0,2(n-i+1-pos)-1\}$，取。无论如何，操作完成之后 $tag'$ 都会变为 $pos$。
• 否则，则意味着我们可以暂时不用管该元素。

处理结束后，弹出栈顶。

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

• 如果其 $pos=pos_p$：

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

  • 如果其 $diff = \text{true}$，我们不用管，因为这意味着 $p$ 上方的元素已经清空了；
  • 否则，其前驱必须成为额外圆盘，处理方法同上。

  处理结束后，弹出栈顶。

• 否则，相当于上面 $diff = \text{false}$ 的情形，同样令其前驱成为额外圆盘。注意此时 $tag'$ 不会减小。

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

• 如果其 $pos=pos_p-1$，将 $diff \gets diff \oplus 1$。
• 否则 $pos_p-1$ 位置对应的元素变得非平凡，插入一个 $pos = pos_p - 1, tag = tag', diff = 1$ 的新元素。

不难验证其正确性。

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