我需要一些帮助来试图找出一些东西:
给定一系列无序数(小于15.000) - A - 我必须回答i,j,x,y形式的Q查询(Q <= 100000),其转换如下:
A中的范围[i,j]中的数字是多于(或等于)x但小于y,且序列中的所有数字都小于5000.
我的印象是这需要类似O(logN)的东西,因为序列的长度很长,这让我想到了BIT(二进制索引树 - 因为查询)但是2D BIT太大而且要求很多即使在更新方面也要运行.所以我在这里看到的唯一解决方案应该是1D BIT或Segment Trees,但我无法想出如何根据这些数据结构制定解决方案.我尝试保留有序数字集中的位置,但我无法弄清楚如何制作响应给定表单查询的BIT.
对于给定的限制,算法也应该适合500ms. 编辑1: 500ms用于预处理和回答查询的所有操作
编辑2:其中i,j是序列A中第一个和最后一个元素的位置,用于查找大于x且小于y的元素
编辑3:示例:让1,3,3,4,6,3和查询1,4,3,5在位置1和4(包括)之间有2个元素(3和4)更大(或相等) )比3小于5
先感谢您!PS:对不起英语不好!