回答对子数组列表的查询

Question

给定一个大小为N的数组A，我们按降序构造一个包含A的所有可能子数组的列表。通过填充零来比较两个子数组B和C，直到它们的大小都是N。然后，我们逐个元素地比较两个子数组，并在观察到一个差异点时立即返回。我们被给出了多个查询，其中给定x，我们必须找到按照上面给出的顺序排序的第x个子数组中的最大元素。例如，如果数组A是3、1、2、4，那么排序的子数组将是：

4.

3、1、2、4

3、1、2

3，1

3.

2，4

2

1、2、4

1，2

1

其中x= 3的查询对应于在子数组3，1，2中查找最大元素；因此，这里的答案将是3。由于查询的数量很大(数量级为10^5)，数组中的元素数量也可能很大(数量级为10^5)，因此我们需要进行一些预处理，以便在O(1)或O(log N)或O(sqrt N)时间内回答每个查询。我似乎想不出该怎么做。当数组包含唯一元素时，我已经解决了这个问题，但是，当数组包含重复元素时，我们如何解决呢？是否有任何数据结构可以帮助存储所需的信息？

Answer 1

按倒序为该数组构建suffix array (将其视为字符串)

对于每个条目存储，它的长度和累积计数(从后缀数组开始的长度总和)

For查询查找所需索引通过二分查找累积计数，并获取所查找后缀的所需前缀

在您的示例中，cumul.counts后缀为

4 (0)
3124 (1)
34  (5)
124  (7)

查询3找到条目3124 (1<=3<5)，并获得前缀(按长度) 3-1=2-nd = 312