对于一堆形如 010110001 的操作，如果你初始知道 01 的答案，并且可以合并两个操作，那么你可以预处理所有长度为 $B$ 的 $01$ 串，然后拼成答案。

这样是 $O(\frac n B + 2^B)$ 的，$B$ 取 $\log n -\log\log n$，可以做到 $O(\frac n {\log n})$。

可以用于例如 +-1 rmq 等地方。

然后考虑你的操作事实上是选两个合并起来。

做 $x$ 步只有 $\displaystyle\prod_{k=1}^x \frac {k(k+1)} 2 $ 种，开 $\log$ 后是 $O(x\ln x)$ 级别。

你要完成的操作的可能都有 $2^n$ 种了，开 $\log$ 后也就是 $n$，所以不可能做的比 $O(\frac n{\log n})$ 更好了。

其实感觉万欧之类的思想和这个有点像。