根据查询计数 [英] Counting according to query

问题描述

鉴于N个​​正元素的数组。让我们假设我们列出所有N×（N + 1）/ 2个非空的连续数组中的一个子阵列，然后更换了所有的最大元素present在各自的子阵列子阵列。所以，现在我们有N×（N + 1）/ 2个元素，每个元素都是最大的子阵中。

现在，我们具有所示Q查询，其中每个查询是3种类型之一：

1 K：我们需要计数数字的严格大于K的情况中的那些N×（N + 1）/ 2个元素

2 K：我们需要计数数字的严格小于K时在那些N×（N + 1）/ 2个元素

3 K：我们需要计数数等于在那些N×（N + 1）/ 2个元素为K的

现在主要的问题现在面临的N可以高达10 ^ 6。所以我不能生成所有的N×（N + 1）/ 2个元素。请帮忙解决这个porblem。

例：设N = 3，我们有Q = 2。设数组A是[1,2,3]那么所有的子数组：

  [1]  - ＆GT; [1]
[2]  - ＆GT; [2]
[3]  - ＆GT; [3]
并[1,2]  -  GT; [2]
[2,3]  -  GT; [3]
[1,2,3]  - ＆GT; [3]
 

所以现在我们有[1,2,3,2,3,3]。为Q = 2这样：

 查询1：3 3
 

这意味着我们需要告诉号数等于3。因此，答案为3，因为有3个数字等于3生成的数组中开始。

 查询2：1 4
 

这意味着我们需要告诉号数大于4。所以答案是0，因为没有人超过4生成的数组中开始。

现在既N及Q可以高达10 ^ 6。那么如何解决这个问题。其中数据结构应适合解决这个问题。

解决方案

我相信我在解决方案O（N + Q *日志N）（更多关于< A HREF =htt​​ps://en.wikipedia.org/wiki/Time_complexity相对=nofollow称号=维基>时间复杂度）。关键是要做到$的很多的的p $ pparation与阵列即使是第一个查询到达之前。

1. 对于每一个数字，找出其中是这个数字的左/右侧的第一个数字，这是严格越大。

例：数组： 1，8，2，3，3，5，1 两个 3 的左块将 8 的位置，右挡会的位置 5 。

这可以在线性时间来确定。这就是：保持一叠previous最大值在堆栈中。如果出现新的最大值，从堆栈中删除最大值，直到你得到一个元素大于或等于当前之一。图：

在本例中，在堆栈： [15，13，11，10，7,3] （当然就可以保持的索引的，不是的值的，我只是用价值更好的可读性）。

现在我们读 8 ， 8'= 3 让我们删除 3 从堆栈和重复。 8'= 7 ，删除 7 。 8示10 ，所以我们不再删除。我们制定 10 为 8 的左边块，并添加 8 的最大值叠加。

此外，当你从堆栈中删除（ 3 和 7 在这个例子中），设置右挡除去号码的当前数目。虽然一个问题：右块将被设置到下一个数大于或等于，不严格更大。你可以用简单的检查和重新链接的右块解决这个问题。

<醇开始=2>

在计算什么数最大的一些子了多少次了。

由于每一个号码，你现在知道哪里是下一个左/右大数目，我相信你找到合适的数学公式这一点。

然后，将结果存储在一个散列表，键是一个数字的值，值将是多少次是数最多的一些子序列。例如，记录 [4- GT; 12] 将意味着数 4 是最大的 12 序列。

最后，提取HashMap中的所有键 - 值对到一个数组和排序数组的键。最后，创建一个 preFIX总和获取的值该排序的数组。

<醇开始=3>

在处理一个请求

有关要求完全 K ，只是在你的阵列二进制搜​​索，因为更多/小于 k` `，二进制搜索键 K 然后使用preFIX阵列。

Given an array of N positive elements. Lets suppose we list all N × (N+1) / 2 non-empty continuous subarrays of the array A and then replaced all the subarrays with the maximum element present in the respective subarray. So now we have N × (N+1) / 2 elements where each element is maximum among its subarray.

Now we are having Q queries, where each query is one of 3 types :

1 K : We need to count of numbers strictly greater than K among those N × (N+1) / 2 elements.

2 K : We need to count of numbers strictly less than K among those N × (N+1) / 2 elements.

3 K : We need to count of numbers equal to K among those N × (N+1) / 2 elements.

Now main problem am facing is N can be upto 10^6. So i can't generate all those N × (N+1) / 2 elements. Please help to solve this porblem.

Example : Let N=3 and we have Q=2. Let array A be [1,2,3] then all sub arrays are :

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

So now we have [1,2,3,2,3,3]. As Q=2 so :

Query 1 : 3 3

It means we need to tell count of numbers equal to 3. So answer is 3 as there are 3 numbers equal to 3 in the generated array.

Query 2 : 1 4

It means we need to tell count of numbers greater than 4. So answer is 0 as no one is greater than 4 in generated array.

Now both N and Q can be up to 10^6. So how to solve this problem. Which data structure should be suitable to solve it.

解决方案

I believe I have a solution in O(N + Q*log N) (More about time complexity). The trick is to do a lot of preparation with your array before even the first query arrives.

1. For each number, figure out where is the first number on left / right of this number that is strictly bigger.

Example: for array: 1, 8, 2, 3, 3, 5, 1 both 3's left block would be position of 8, right block would be the position of 5.

This can be determined in linear time. This is how: Keep a stack of previous maximums in a stack. If a new maximum appears, remove maximums from the stack until you get to a element bigger than or equal to the current one. Illustration:

In this example, in the stack is: [15, 13, 11, 10, 7, 3] (you will of course keep the indexes, not the values, I will just use value for better readability).

Now we read 8, 8 >= 3 so we remove 3 from stack and repeat. 8 >= 7, remove 7. 8 < 10, so we stop removing. We set 10 as 8's left block, and add 8 to the maximums stack.

Also, whenever you remove from the stack (3 and 7 in this example), set the right block of removed number to the current number. One problem though: right block would be set to the next number bigger or equal, not strictly bigger. You can fix this with simply checking and relinking right blocks.

2. Compute what number is how many times a maximum of some subsequence.

Since for each number you now know where is the next left / right bigger number, I trust you with finding appropriate math formula for this.

Then, store the results in a hashmap, key would be a value of a number, and value would be how many times is that number a maximum of some subsequence. For example, record [4->12] would mean that number 4 is the maximum in 12 subsequences.

Lastly, extract all key-value pairs from the hashmap into an array, and sort that array by the keys. Finally, create a prefix sum for the values of that sorted array.

3. Handle a request

For request "exactly k", just binary search in your array, for more/less thank``, binary search for key k and then use the prefix array.

这篇关于根据查询计数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！