查找最近的未取元素的数据结构

Question

我有一个数组A[0…N-1]包含N个元素和一个包含M个索引的列表。列表中的每个索引对应于数组中的一个元素。例如，索引为0对应A[0]，索引为1对应A[1]

我想按顺序处理列表，从第一个索引到最后一个索引，如下所示:
对于当前索引I，

1. 如果不采取[我],[我]将。
2. 如果取A[i]，则最小的j>如果A[j]没有取，则取A[j]。如果没有此元素，输出-1

我想输出一个长度为M的数组B，其中B[I]表示所取元素的索引。我想知道如何在线性复杂度中做到这一点。(即O(N)或O(M))。可以使用什么数据结构?

Answer 1

这是一个O(M*logM)算法的建议。

开始时，将列表的所有M个索引插入允许双精度的排序树中。步骤变成，

1. 如果A[i]未取，则取A[i]。从树中删除i。
2. 如果取A[i]，则最小的j>如果A[j]没有取，则取A[j]。最小的j>i在树的i之后很容易得到。如果没有这样的j，输出-1。否则，从树中删除j。