Set

$O(nlogn)$

C++ 代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010, INF = 1e9;

int ans[N], n;

set<PII> s; //维护连续的区间

// 此算法的时间复杂度取决于n, 与元素的大小无关, O(nlogn)

int main(){
    scanf("%d", &n);
    s.insert({1, INF});
    int x;
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        auto iter = s.lower_bound({x, INF});
        if(iter == s.end()) --iter;
        // 分类讨论 (判断x是否被区间覆盖)
        int l = iter->first, r = iter->second;

        if(l <= x && r >= x){   //如果当前区间完全覆盖x,则以x为分割点分割出新的连续区间
            s.erase(iter);
            if(x - 1 >= l) s.insert({l, x - 1});
            if(x + 1 <= r) s.insert({x + 1, r});
            ans[i] = x;
            }
        else{   //若前面有区间,再判断是否覆盖x
            if(iter == s.begin() && l > x){ //前面无区间,将x增加至当前区间左边界
                ans[i] = l;
                s.erase(iter);
                if(l + 1 <= r) s.insert({l + 1, r});
                }
            else{
                --iter;
                int l = iter->first, r = iter->second;
                if(l <= x && r >= x){   //当前区间完全覆盖x,处理方式同上
                    s.erase(iter);
                    if(x - 1 >= l) s.insert({l, x - 1});
                    if(x + 1 <= r) s.insert({x + 1, r});
                    ans[i] = x;
                    }
                else{   //增长至原区间的左边界
                    ++iter;
                    ans[i] = iter->first;
                    if(iter->first + 1 <= iter->second) 
                        s.insert({iter->first + 1, iter->second});
                    s.erase(iter);
                    }
                }
            }
        }

    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
    puts("");
    return 0;
}