arrays - 按查询计数

Question

给定一个包含 N 个正元素的数组。假设我们列出了数组 A 的所有 N × (N+1)/2 个非空连续子数组，然后用相应子数组中存在的最大元素替换了所有子数组。所以现在我们有 N × (N+1)/2 个元素，其中每个元素在其子数组中都是最大值。

现在我们有 Q 个查询，其中每个查询都是 3 种类型之一:

1 K :我们需要统计这 N × (N+1)/2 个元素中严格大于 K 的数。

2 K :我们需要统计这 N × (N+1)/2 个元素中严格小于 K 的数。

3 K :我们需要计算这 N × (N+1)/2 个元素中等于 K 的数字。

现在面临的主要问题是 N 最多可以达到 10^6。所以我无法生成所有这些 N × (N+1)/2 个元素。请帮忙解决这个问题。

示例:设 N=3，我们有 Q=2。令数组 A 为 [1,2,3]，则所有子数组为:

[1] -> [1]
[2] -> [2]
[3] -> [3]
[1,2] -> [2]
[2,3] -> [3]
[1,2,3] -> [3]

所以现在我们有 [1,2,3,2,3,3]。由于 Q=2 所以:

Query 1 : 3 3

这意味着我们需要告诉数字的计数等于 3。所以答案是 3，因为生成的数组中有 3 个数字等于 3。

Query 2 : 1 4

这意味着我们需要告诉大于 4 的数字的计数。所以答案是 0，因为生成的数组中没有一个大于 4。

现在 N 和 Q 都可以达到 10^6。那么如何解决这个问题。应该适合用什么数据结构来解决。

Answer 1

我相信我在 O(N + Q*log N) 中有解决方案(更多关于 time complexity )。诀窍是在第一个查询到达之前对您的数组进行大量准备工作。

1. 对于每个数字，找出该数字左侧/右侧第一个严格更大的数字在哪里。

示例:对于数组:1, 8, 2, 3, 3, 5, 1两者 3的左 block 将是 8 的位置, 右 block 将是 5 的位置.

这可以在线性时间内确定。方法如下:在堆栈中保留一堆以前的最大值。如果出现新的最大值，则从堆栈中删除最大值，直到找到大于或等于当前元素的元素。插图:

在这个例子中，栈中是:[15, 13, 11, 10, 7, 3] (您当然会保留索引，而不是值，我将使用值来提高可读性)。

现在我们读到8 , 8 >= 3所以我们删除 3从堆栈中重复。 8 >= 7 , 删除 7 . 8 < 10 ，所以我们停止删除。我们设置 10作为8的左侧 block ，并添加 8到最大值堆栈。

此外，无论何时从堆栈中移除(本例中为 3 和 7)，将移除数字的右侧 block 设置为当前数字。但是有一个问题:右边的 block 将被设置为下一个更大或相等的数字，而不是严格意义上的更大。您可以通过简单地检查和重新链接正确的 block 来解决这个问题。

1. 计算某个子序列的最大值是多少。

因为对于每个数字，您现在都知道下一个左/右更大的数字在哪里，我相信您会为此找到合适的数学公式。

然后，将结果存储在 HashMap 中，键将是一个数字的值，而值将是该数字是某个子序列的最大值的次数。比如记录[4->12]将意味着这个数字 4是 12 中的最大值子序列。

最后，将 HashMap 中的所有键值对提取到一个数组中，并按键对该数组进行排序。最后，创建一个 prefix sum对于该排序数组的值。

1. 处理请求

对于“恰好 k”的请求，只需在您的数组中进行二分查找，即 more/less than k``，二进制搜索键 k然后使用前缀数组。