计算连续糖果的数量

Question

我正在尝试解决定义如下的问题：

A candy is represented by a number from 1 to 1e6. A person is said to have a set of k candies if he has candy 1 to k.

E.g. If a person bought candies 1, 2 and 6, then he has a set of 2 candies

Given 2 types of operations: Eat x and Buy x where x represents the candy number. Buy x will increase the quantity of x by 1 only. Eat x will decrease the quantity of x by 1 only.

For each operation, answer the question, what is the size of the set of candies that I have now?

我正在尝试找到最有效的方法来做到这一点。我想到的解决方案如下：

令 count[i] 定义大小为 1 - N 的数组，其中 N 是可能的最大糖果数。 count[i] 存储我目前拥有的编号为 i 的糖果的数量。

设大小为 1 - N 的 Fenwick[i] 数组，其中 N 是可能的最大糖果数。这个数组是为了构建一个fenwick树来存储我的collection中糖果的累计和。此累加和不使用计数数组。累计和计数 1 的数量（每个 1 表示糖果 x 存在于我的 collection 中）。例如如果我有一组5颗糖果，那么1到5的累计和是5。如果有一组10颗糖果，那么1到10的累计和是10...

对于购买操作，如果糖果 x 不在我的 collection 中，则从索引 x 开始向累积和加 1（这由 fenwick 树处理）。否则，我将只执行 count[x]++

对于吃操作，执行count[x]--。如果 count[x] 现在是 0，那么我从索引 x 开始从累积和减 1（这由 fenwick 树处理）。

至此，插入和删除的部分就解决了。困难的部分是如何获得当前 collection 中糖果集的大小。

我尝试在Fenwick树上查询最大索引i，从1到i的累积和等于i，同时每次以2的幂递增我的查询索引。

我取最大的索引，它是一组有效的糖果，j，最小的索引是无效的 collection 糖果，k。然后从 j 循环到 k，在每次迭代中查询 fenwick 树。一旦循环遇到无效 collection，中断并输出答案。

我觉得这行得通。然而，这当然不是一种有效的方法。有谁能启发我更好的解决方案吗？提前致谢。

编辑（解决方案）：

我的插入和删除方法是正确的。只是我用错误的方式搜索了 collection 的糖果。在这种情况下，我们想要最大的数 x，其中 query(x) = x（query(x) 给出从 1 到 x 的累加和）。所以我们可以使用二分查找找到x的最大有效值(query(x) = x)。为此，我们只需要保留一个额外的变量来跟踪 x 的最后一个值，其中 query(x) 给出有效的 collection.

解的复杂度：O(log^2(N))

Answer 1

这是典型的二叉树结构。

为简单起见，假设糖果的索引范围从 0 到 2^k - 1 为某个整数 k。然后每时每刻状态由16个数字表示，c[0]到c[2^k - 1]，其中c[i]是糖果的数量i。

我们构造一棵二叉树如下：根节点P(0, 2^k)代表整个区间[0, 2^k)；对于满足b - a > 1的每个节点P(a, b)，构建两个子节点P(a, (a + b)/2)和P((a + b)/2, b).

设 p(a, b) 为区间 [a, b) 中 i 的 c[i] 的最小值。显然我们有：

p(a, a + 1) = c[a];
p(a, b) = min{p(a, (a + b)/2), p((a + b)/2, b)} 如果 b - a > 1.

构建此数据结构后，对于每个操作（加一或减一），我们可以从下到上按 O(k) 步更新数据。此外，找到糖果集的大小也可以在 O(k) 步中完成。

数据结构示例：

我们来看k = 3的情况，这样就有c[0]到c[7]。例如：

c[0 .. 7] = {1, 3, 0, 4, 3, 2, 8, 1}

树形结构如下所示：

p(0, 8) = 0
|- p(0, 4) = 0
|  |- p(0, 2) = 1
|  |  |- p(0, 1) = 1
|  |  |_ p(1, 2) = 3
|  |_ p(2, 4) = 0
|     |- p(2, 3) = 0
|     |_ p(3, 4) = 4
|_ p(4, 8) = 1
   |- p(4, 6) = 2
   |  |- p(4, 5) = 3
   |  |_ p(5, 6) = 2
   |_ p(6, 8) = 1
      |- p(6, 7) = 8
      |_ p(7, 8) = 1

现在假设我们将1加到c[2]，变成1，那么我们只需要更新p(2, 3)，[=42] =], p(0, 4), p(0, 8).

计算连续糖果的数量

Count number of consecutive candies

algorithm

fenwick-tree