有效地插入阵列后，找到每个元素的地板和天花板

Question

假设数组具有元素[1,n]。元素(m查询(的连续输入一一。如下。

1. 5因此，您必须将1打印为地板，而ceil则必须打印1，然后阵列变为 [1,5,10]
2. 2因此打印1作为地板，5个为Ceil和Array变为[1,2,5,10]

像这样的查询。地板和天花板，可以在我们保持阵列清单上排序时使用O(log n(时间复杂性找到。

但问题是找到插入的元素位置是O(log n)，在最坏情况下移动其他数字的插入为O(n)，这会导致每个查询的O(log n) + O(n)。

因此，对于最坏的情况，对于m查询，它将是mxO(logn + n)，它太昂贵了。我希望此操作有效地比mxO(logn + n)。

Answer 1

而不是数组，您应该使用平衡的二进制搜索树。插入和下限/上限(即"地板"one_answers" ceil"(全部完成了O(log n)，总运行时为O(m log m)。

您没有提及该语言，但例如，使用C set容器(实现了二进制搜索树(，代码看起来像这样：

std::set<int> A;
A.insert(1);
A.insert(n);
for(int i = 0; i < m; ++i) {
    int x;
    scanf("%d", &x);
    assert(1 < x && x < n);
    auto iter = A.insert(x).first;
    printf("floor: %d, ceil: %dn", *prev(iter), *next(iter));
}