不同数字的乘积之和及其计数

Question

给定一个包含 N 个元素的数组，其中 N 最大为 200000。数组元素最多为 100000。现在我们提供 [a b] 形式的 Q 查询。对于每个查询，我们需要告诉总和：

((Count of each distinct number in range a to b)^2)*(Value of that distinct number)

示例令 N=8，数组为 [1 1 2 2 1 3 1 1]，令 Q=1。这意味着只有一个查询。令a=2，b=7，则答案为20

解释 :

occurrence of 1-> 3
occurrence of 2-> 2
occurrence of 3-> 1
cost=3*3*1 + 2*2*2 + 1*1*3= 20

现在，如果查询比它少，问题就不会那么难了。但是 Q 可以达到 200000。那么什么数据结构最适合这个问题？

Answer 1

这是一个离线的 O((n + q) * sqrt(n)) 解决方案：

让我们将给定的数组分成 sqrt(n) 个连续的块，每个块有 sqrt(n) 个元素。
让我们根据包含其左边框的块的数量来划分所有查询。
现在我们将分别回答每个组的问题：
- 在一组中，我们应该按右边界（递增顺序）对查询进行排序。
- 让我们按排序顺序遍历该组中的所有查询并保持以下不变性：位于该查询覆盖的块内的所有数字，可能除了第一个和最后一个块，已经处理。我们可以在需要时通过处理下一个块来维护它。
- 鉴于此不变量，我们可以通过仅查看第一个和最后一个块（包含此查询的边界）中的数字来获得此查询的答案。最多有 O(sqrt(n)) 个这样的数字，所以我们可以简单地迭代它们。
- 说明：我们维护一个大小为MAX_VALUE的数组count，其中count[i]是处理后的数字中i出现的次数和 curSum - 处理数字的目标函数的总和。我们可以在O(1)中增加或减少一个数字：增加或减少count[i]和调整curSum。该数字已处理意味着它已被考虑在 count 数组和 curSum 变量中。

时间复杂度：对于每一组，我们一次从左到右遍历数组，处理内部块中的数字。需要 O(n * sqrt(n)) 次。每个查询都会提供额外的 O(sqrt(n)) 时间来处理此查询的第一个和最后一个块中的数字。因此，总时间复杂度为O((n + q) * sqrt(n))。

Sum of product of distinct numbers and their count