SubArray 中的相等元素

Question

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

例如：

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，我们将答案增加范围内的索引总和 - (#occurrences of x in range * i)，然后增加总和和出现次数。其他三个操作类似。

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

Answer 2

创建一个映射，其键是数组元素，值是它们出现位置的列表（您的示例将变为 {0: [0, 2, 4, 6], 8: [3], 4: [1], 32: [5]}）。这些组形成不相关的问题。找到答案的一种方法是将它们视为 maximum flow problems，其中每个索引形成两个个顶点。
每个索引都连接到它后面的所有索引，并且它之前的所有索引都连接到它。边的权重是数组中元素的距离，即两个索引之间的差异。所有 "source" 个顶点都连接到一个无限源，所有 "destination" 个顶点都连接到一个汇。
所有问题的最大流量值的总和就是您要查找的总和。

例如，让我们使用项目 0:

的索引

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


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

请注意，边的数量增长为 V^2，因为每条边都对应于您为计算结果而必须做的差异，这些差异位于每个索引及其所有后继之间。这使得解决方案的复杂度 O(n^3) 甚至比朴素算法还要糟糕，这只是从另一个角度看问题的好方法:)

SubArray 中的相等元素

Equal elements in SubArray

python

c++

algorithm

data-structures

bit-manipulation