给出一组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.那么如何解决这个问题呢.哪种数据结构应该适合解决它.