SubArray中的等量元素

Question

我有一个包含N个元素的数组，我需要找到子数组中相等元素的索引之间的距离；这将以查询(L )的形式得到，其中L是子数组的索引，而R是结束索引的索引。总数数组元素可以是N<=10^5和查询Q<=10^5。

ex:

7

0 4 0 8 0 32 0

2

0 2

0 5

第一次查询的//应答为2(索引2-0)

第二个查询的答案是8(索引(2-0) + (4-2) + (4-0))

编辑：我不希望代码(虽然这会非常有用)解决一般想法将是一个很大的帮助。

Answer 1

这是用于sqrt分解的工作。

我们希望保持允许我们回答当前范围和调整当前范围的端点的状态。为此，我们维护一个从元素到(当前范围内该元素的所有索引之和，当前范围内出现的次数之和)的映射。我们也维持目前的答案。为了向下调整较低的端点以包含索引i处的元素x，我们在范围内按索引之和增加答案-(在范围*i中x的出现次数#)，然后增加和次数。另外三种操作是相似的。

为了实现sqrt分解，我们对查询按(下端点层除以sqrt，上端点)进行排序，并按顺序调整范围。

Answer 2

创建一个映射，其键是数组的元素，值是它们出现在其中的位置的列表(您的示例将成为{0: [0, 2, 4, 6], 8: [3], 4: [1], 32: [5]})。这些群体构成了不相关的问题。找到答案的一种方法是将它们看作是最大流问题，其中每个索引形成两个顶点。

每个索引连接到它后面的所有索引，它之前的所有索引都连接到它。边的权重是数组中元素的距离，即两个索引之间的差异。所有“源”顶点都连接到无限源，所有“目标”顶点都连接到接收器。

所有问题的最大流的值之和是您正在寻找的总和。

作为示例，让我们使用项0的索引

           +-------- 0 ----------+      0 --------+
           |                     |                |
           |                     |                |
Source ----+-------- 2 -------+  +----> 2 --------+---- Sink
           |                  |  |                |
           |                  |  |                |
           +-------- 4 ----+  +--+----> 4 --------+
           |               |  |  |                |
           |               |  |  |                |
           +-------- 6     +--+--+----> 6 --------+


Weight of arc (u, v) = v - u

请注意，边的数量以V^2的形式增长，因为每个边对应于计算结果的差异，这是在每个索引和它的所有后继者之间进行的。这使得解决方案O(n^3)的复杂性比朴素算法更糟糕，它只是从另一个角度看待事物的一个很好的方法:)