比特操作:更难翻动硬币

最近,我在CodeChef上看到了这个名为“翻动硬币”的问题(链接: FLIPCOINS )。

总之,有N个硬币,我们必须编写一个支持两个操作的程序。

1. 在[A,B]范围内投掷硬币
2. 分别求出[A,B]范围内的磁头数。

当然,我们可以快速使用段树(范围查询、使用延迟传播的范围更新)来解决这个问题。

然而,我遇到了另一个类似的问题,在一系列翻转之后(操作1),我们需要输出翻转后产生的硬币排列(例如100101,其中0代表头部,1代表尾部)。

更具体地说,操作2从计算头数变为生成所有N个硬币的最终排列。此外,新的操作2是 只有 在之后调用 全部的 翻转已完成(即操作2是最后一次调用,并且只调用一次)。

我可以知道怎么解决这个问题吗?根据问题标签,它需要某种形式的位操作。

编辑

我试图通过所有查询强制执行,唉,它超出了时间限制。