根据查询计数

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)（更多关于时间复杂度）。诀窍是在第一个查询到达之前就对数组进行大量准备。

示例：对于数组：1, 8, 2, 3, 3, 5, 1两者3的左块将是的位置8，右块将是的位置5。

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

在此示例中，堆栈中是：（[15, 13, 11, 10, 7, 3]当然，您将保留索引，而不是值，我将仅使用值以获得更好的可读性）。

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

此外，每当您从堆栈中删除时（3在7本例中），请将删除的数字的右侧块设置为当前数字。但有一个问题：右块将被设置为下一个更大或等于的数字，而不是严格意义上的更大。您可以通过简单地检查和重新链接正确的块来解决此问题。

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

然后，将结果存储在 hashmap 中，key 是一个数字的值，value 是该数字最多是某个子序列的多少次。例如，记录[4->12]意味着该数字4是最大的12。

最后，将哈希图中的所有键值对提取到一个数组中，并按键对该数组进行排序。最后，为该排序数组的值创建一个前缀和。

对于“完全”请求k，只需在数组中进行二分搜索，对于more/less thank``，对键进行二分搜索k，然后使用前缀数组。