连续糖果数

Question

我正试图解决以下问题：

糖果由一个从1到1e6的数字表示。如果一个人有1比k的糖果，据说他有一套k糖果。 如果一个人买了糖果1，2和6，那么他就有一套2块糖果。 给定两种类型的操作: Eat x和Buy，其中x代表糖果号。购买x只会使x的数量增加1。吃x只会使x的数量减少1。 每一次手术，回答以下问题:我现在拥有的一套糖果的大小是多少？

我正在努力寻找最有效的方法来做到这一点。我想出的解决办法如下：

让我们定义大小为1-N的数组，其中N是最大的糖果数。康提用我到目前为止拥有的I号来存储糖果的数量。

假设芬威基阵列的大小为1-N，其中N是最大的糖果数。这个数组用于构造一棵芬威克树，以存储我收集的糖果的累积和。此累积和不使用计数数组。累积和计数数量为1s (每个1表示在我的收藏中存在一个糖果x)。如果我有一套5种糖果，那么1到5的累积和是5。如果有10种糖果，那么从1到10的累计金额是10…

对于购买操作，如果糖果x还没有在我的集合中，从索引x开始添加1到累积和(这是由芬威克树处理)。否则，我将只执行countx++

对于eat操作，执行countx--。如果countx现在是0，那么从索引x开始，我从累积和中减去1(这是由fenwick树处理的)。

这就解决了插入和删除的部分。最困难的部分是如何获取当前收藏中的一组糖果的大小。

我试图查询芬威克树中最大的索引i，其中从1到I的累积和等于i，同时每次以2的幂递增我的查询索引。

我取最大的索引，是一组有效的糖果，j，最小的索引，是一个无效的糖果集合，k，然后从j循环到k，在每次迭代中查询芬威克树。一旦循环命中无效的集合，中断并输出答案。

在我看来，这是可行的。然而，这肯定不是一个有效的方法。有人能告诉我一个更好的解决办法吗？提前谢谢。

编辑(解决方案)：

我的插入和删除方法是正确的。我只是在用不正确的方式寻找糖果的收藏。在这种情况下，我们需要最大的数字x，其中query(x) =x (query(x)给出了从1到x的累积和)。因此，我们可以使用二进制搜索找到x的最大有效值(query(x) = x)。为了实现这一点，我们只需要保留一个附加变量来跟踪查询(X)提供有效集合的x的最后一个值。

解的复杂性: O(log^2(N))

Answer 1

这通常是一个二叉树结构。

为了简单起见，让我们假设糖果的索引范围从0到2^k - 1 (对于某些整数k )。然后，在每个时刻，状态都由16数字表示，c[0] to c[2^k - 1]，其中c[i]是糖果i的数字。

我们构造一个二叉树如下:根节点P(0, 2^k)表示整个区间[0, 2^k)；对于每个节点P(a, b)，如b - a > 1，构造两个子节点P(a, (a + b)/2)和P((a + b)/2, b)。

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

• p(a, a + 1) = c[a]；
• 如果为b - a > 1，则为p(a, b) = min{p(a, (a + b)/2), p((a + b)/2, b)}。

在构造了这个数据结构之后，对于每个操作(加上一个或减去一个操作)，我们可以从下到上以O(k)步骤更新数据。此外，在O(k)步骤中也可以找到一组糖果的大小。

数据结构示例：

让我们看一看案例k = 3，这样就有了c[0] to 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)、p(2, 4)、p(0, 4)、p(0, 8)。