algorithm - 使用 Scala 抛硬币

Question

我正在尝试通过 scala 中的 codechef 解决 Flipping coins 问题。问题陈述如下:

There are N coins kept on the table, numbered from 0 to N - 1. Initally, each coin is kept tails up. You have to perform two types of operations : 1) Flip all coins numbered between A and B. This is represented by the command "0 A B" 2) Answer how many coins numbered between A and B are heads up. This is represented by the command "1 A B". Input : The first line contains two integers, N and Q. Each of the next Q lines are either of the form "0 A B" or "1 A B" as mentioned above.

Output : Output 1 line for each of the queries of the form "1 A B" containing the required answer for the corresponding query.

示例输入:

 4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3 
1 3 3

Sample Output :

0
1
0
2
1

Constraints : 1 <= N <= 100000 1 <= Q <= 100000 0 <= A <= B <= N - 1

以最简单的方式，我正在考虑在 scala 中初始化一个 Int 数组，如下所示:

 var coins = new Array[Int](1000)

如果遇到命令0 A B，我会简单的把A到B+1的索引设置为1，如下:

 for(i <- 5 until 8){
      coins(i) = 1
    }

如果我遇到命令 1 A B，我将从 A 到 B+1 的数组中取出一部分，并计算该给定切片中 1 的数量，我将按如下方式进行:

val headCount = coins.slice(5,8).count(x => x == 1)

看起来这个操作在最坏的情况下需要 O(n)，显然这可以优化为在对数时间内解决。

有人可以指出我在这里可能做错了什么以及如何以最佳方式解决这个问题。

谢谢

Answer 1

这些天我对 scala 了解不多，但我可以建议一个关于 O(log(n)) 的更一般问题的答案。通常此类算法使用树，我认为您可以在此处这样做。

如果你构造一棵平衡树，以硬币作为叶子，那么你可以在每个节点中存储硬币总数和该节点下方叶子中的正面数。你可以想象抛硬币的代码从节点信息中计算出要访问的叶子，并在 O(n) 时间内工作(你仍然需要抛硬币)。但是如果翻转代码也更新了节点数据，那么头的数量将为 O(log(n))，因为您可以使用节点信息 - 您不需要去叶子。

这样一来，一个命令的复杂度为 O(n)，另一个命令的复杂度为 O(log(n))。

但你可以做得更好。我认为你也可以进行翻转操作 O(log(n))。为此，您需要向每个节点添加一个“翻转”标志。如果设置，则翻转该点以下的所有节点。有一些簿记细节，但总体思路就在那里。

如果您得出其合乎逻辑的结论，您实际上不需要存储树叶，至少在开始时是这样。您只需在处理命令时添加具有所需详细程度的节点。至此，你基本上已经有了评论中提到的区间树。