c++ - 位操作 : Harder Flipping Coins

Question

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

综上所述，有N个硬币，我们必须编写一个支持两种操作的程序。

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

当然，我们可以快速使用线段树(范围查询，使用惰性传播的范围更新)来解决这个问题。

但是，我遇到了另一个类似的问题，在一系列翻转(操作 1)之后，我们需要输出翻转后的硬币排列结果(例如 100101，其中 0 代表正面，而 1 代表尾部)。

更具体地说，操作 2 从计算正面的数量变为生成所有 N 个硬币的排列结果。此外，新操作 2 仅在所有翻转完成后调用(即操作 2 是最后调用的并且仅调用一次)。

我可以知道如何解决这个问题吗？根据问题标签，它需要某种形式的位操作。

编辑

我尝试通过所有查询进行暴力破解，唉，它产生了超过时间限制。

Answer 1

可以使用二叉索引树打印出硬币的状态:

• 最初所有的值都是0。
• 当我们需要掷硬币[A, B]时，我们将A递增1并且将 B + 1 减去 1。
• 硬币 i 的状态是 i 模 2 的前缀和。

这是有效的，因为 i 处的前缀总和始终是 i 处完成的翻转操作数。