很有意思的题目，并没有想象的那么难。
首先，为了方便起见，我们可以认为只有两种颜色的球，记为 \(0/1\)。考虑如何将 \(0/1\) 分开，之后多次重复这一过程，每次将部分颜色的球看作 \(1\) 即可。
考虑到要将所有颜色移到同一列中，首先要将将一个目标列中的 \(0/1\) 给“分离”出来。
方法很简单：考虑该列中 \(1\) 的个数为 \(x\)，则如下操作：
- 将一个满列上方的 \(x\) 个球移至空列 （\(x\) 步）
- 将目标列的 \(0\) 放入空列，\(1\) 放入满列（分离）（\(m\) 步）
- 将这些球“倒回”目标列（ \(m\) 步）
- 将空列球还原（\(x\) 步）
一共有 \(2m+2x\) 步。这是还原的基本操作，称为“提取”。
如果直接利用该过程暴力算，进行一些优化可以获得 \(70pts\)
然后，就有几种不同的思路：
一 （感谢 QwQcOrZ 提供）
可以发现，这种方法操作次数与限制次数相差常数级别。
原来的做法还有优化空间，因为我们发现其实用 \(m+x\) 已经成功分离了该列的 \(0/1\)。因此，考虑如何“不还原”。方法很简单：让所选列为全 \(0\) 列。
因为 \(0\) 的数量远大于 \(1\) 所以构造很简单：分离第一列后再分离第二列即可（前两列中 \(0\) 的个数 \(\geq m\)）。
这样，常数就优化了一半，最多 \(60,0000\) 次。
当然，要特判 \(n=2\) 的情况。
二 (大多数题解的分治方法)
考虑将“颜色”的编号设一个阈值，超过为 \(0\)，未超过为 \(1\)。
考虑每次将序列划成两段，左边为 \(0\)，右边为 \(1\)，再分治左右两边。
只需考虑“划分 \(0/1\)”即可。每次只考虑两列。
考虑以多补少。用错误的球较多的一列（ \(i\) ）补齐较少的一列（ \(j\) ）。
对 \(j\) 进行提取（错误球在上方），并将错误球放入空列，再分离 \(i\) 列，最后还原 \(i\) 的位置。
标签：颜色,P7115,分离,放入,移球,还原,NOIP2020,空列,考虑 From： https://www.cnblogs.com/pref-ctrl27/p/16899936.html