赛时队友把这题丢给我说他们去写 B，然后我成功成为了战犯。
首先考虑一个朴素的暴力，建出一个类似线段树的结构。然后每次合并两个儿子节点，操作次数为 $n\log n$，大约需要 1e7 次操作，不能通过。
这时候有一个思路，如果一个区间里的东西比较满，就会让它很慢。但是如果区间比较满，那么重复位置的元素比较多，就可以先处理一半然后平移出来，然后合并三个块，但是要合并的块数变成了三个，比较不好实现（并且预计是常数比较大的 $\frac{1}{2}\log n$），我赛时并没有成功实现这个做法，如果它能过或者不能过可以在评论区留言。
另一种想法是考虑平衡复杂度。具体的，我们选取一个比较小的 $B$ ，那么长度为 $B$ 的区间种类为 $2^B$ 也不会很大。我们考虑对于每一种长度为 $B$ 的区间处理出他们是 1 的位中某一位的集合，那么通过平移就可以得到其他位的集合，这部分的操作次数是 $\frac{n}{B}\log n+n$。然后我们现在有 $B2^B$ 个区间，将他们用类似于合并果子的思路合并，操作次数不超过 $n\log {B2^B}$。取 $B=\sqrt {\log n}$，操作次数为 $n\sqrt{\log n}$，可以通过此题。