题解：P7115 [NOIP2020] 移球游戏

暑假 vp 的时候连 $n=2$ 的常规解法都没想到，于是一波爆搜强行构造 $n=2$ 方案喜提 $10$ 分。

当时还不会按照值域 $0/1$ 分治的 trick，不过后来见到了无数次这种 trick。

我印象中这个题也是分治构造的。 P9731 [CEOI2023] Balance

下文中将柱子称为栈 $s$，毕竟两者的用法是一样的。

先思考 $n=2$ 时候的解法，记录两个栈为 $s_1$ 和 $s_2$，分别目标为 $1$ 球和 $2$ 球。我们现在想要其中一个栈变成全 $1$。我们发现 $s_1$ 和 $s_2$ 都往空栈里面放一点东西进去似乎只有暴搜放进去的顺序然后 $2$ 和 $3$ 栈互相搞一下的很暴力的做法，没有可扩展性。

有没有什么好办法去分离 $1$ 和 $2$ 两种小球呢，只有两个空栈能办到。我们现在只有一个空栈，转念一想，其实我们可以再创造两个半空栈，设 $s_1$ 中有 $a$ 个 $1$，那么我们只需要从 $s_1$ 中挪 $\min(a,m-a)$ 个球给 $s_3$。不妨设 $a<m-a$，然后将 $s_1$ 中球依次弹出，如果是 $1$ 则放入 $s_2$ 中，如果是 $0$ 则放入 $s_3$ 中，这次操作把部分 $0$ 和 $1$ 聚集在了一起。

接着，把 $s_2$ 和 $s_3$ 栈顶的 $0/1$ 段全部再放回 $s_1$ 中，这一步我们实现了对于 $s_1$ 的排序。

将 $s_2$ 中的所有数移动到 $s_3$ 中，再把 $s_1$ 中顶端的 $1$ 段放入 $s_2$ 中。这一步我们实现了将 $0$ 和 $1$ 段分别独立地放在 $s_1$ 和 $s_2$ 中。

然后就是处理 $s_3$ 了，我们只需要根据是 $0$ 还是 $1$ 分别放入 $s_1$ 或者 $s_2$ 即可。

这样子我们就完美解决了 $n=2$ 的情况。

那么对于 $n>2$ 的时候呢？把问题转化到 $n=2$！

我们设 $\operatorname{solve}(l,r)$ 表示正在处理颜色为 $[l,r]$ 范围内的球。我们将 $x\le mid$ 的球全部看成一种颜色，将 $x>mid$ 的球看成另一种颜色，然后执行 $n=2$ 的算法就可以将 $x\le mid$ 的球放在一起，$x>mid$ 的球放在一起，然后再分别进行操作 $\operatorname{solve}(l,mid)$ 和 $\operatorname{solve}(mid+1,r)$ 就可以继续分治下去解决问题了。