考场上连\(n=2\)都不会。
在场外想\(n=2\)也花了一定时间。
现在看到快排后随便想一下就想出来了。
考虑快排。选择一个中心\(md\)，维护两个集合\(s1,s2\)，把\(\leq md\)的所有球放入\(s1\)，其他放入\(s2\)。
注意到这样子我们只需要关注球的权值是否\(\leq md\)。
所以问题转化成了我们把所有\(\leq md\)和\(>md\)的球分成独立的，颜色相同的柱子，也就是\(n=2\)的强化版。
先考虑\(n=2\)。
如果\(n\)为奇数（偶数类似），则把第一个柱子分成\([1,n/2],[n/2+1,n]\)两个部分，第二个柱子分成\([1,(n+1)/2],[(n+1)/2+1,n]\)。
先考虑第一个柱子的\([1,n/2]\)和第二个柱子的\([1,(n+1)/2]\)。
显然这两个部分存在一种颜色的大小\(\geq (n+1)/2\)，设为\(x\)
可以使用空柱子。把第一个柱子的\([1,n/2]\)和第二个柱子的\([1,(n+1)/2]\)全部插到空柱子。
然后从空柱子的顶部开始考虑，如果颜色是\(x\)，则放到第二个柱子，否则放到第一个柱子。
使用\(2m\)次操作。
显然这样子，第二个柱子的\([1,(n+1)/2]\)的部分一定全是颜色\(x\)，第一个柱子上存在一个分界线，使得分界线上全是\(x\)，其他全是和\(x\)相反的颜色
然后翻转第二个，第一个柱子，显然可以把全部插到空柱子上完成。
使用\(4m\)次操作。
然后对第二个/第一个柱子的顶部继续如此操作。
使用\(2m\)次操作。
把第二个柱子翻转（或者不翻转），使得第二个柱子的顶部颜色和第一个柱子相同，这个颜色设为\(y\)。
使用\(2m\)次操作。
把第二个/第一个柱子上面的所有颜色\(y\)插入到一个新的柱子上，再把第二个柱子上的剩余颜色（设为\(z\)）全部插到第一个柱子上，再把新柱子上的颜色全部插到第二个柱子上，如果不够插就插到第一个柱子。
使用\(2m\)次操作。
对于多个柱子的情况，检测哪个柱子是相同颜色的，把它删除，执行\(n\)次即可。
这样子我们成功的把两个柱子球分成颜色相同的柱子。
常数非常大，但是感觉还是可过。
原文：https://www.cnblogs.com/ctmlpfs/p/14107813.html