法1：

用map去维护那些已经被使用过的区间:key为左端点，val为右端点。
这样我们可以用map的API:upper_bound快速找到比t大的区间，然后就可以判断t是否在它前面一个区间pre里面。
在pre范围内，只能用pre的右端点+1；不在就可以直接使用这个值。
然后就需要分类讨论，合并区间。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<climits>
#define x first
#define y second
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

static const int N = 1e6 + 5;
int fa[N], n;
map<int, int> rec;

int main(void){
    cin >> n;
    int t;
    for (int i = 0; i < n; i++){
        scanf("%d", &t);
        auto pos = rec.upper_bound(t);
        auto org = pos;
        int r;
        if (pos == rec.begin()) {
            printf("%d ", t);
            auto next = rec.upper_bound(t);
            if (next != rec.end() && next->first == t + 1) {
                rec.insert(MP(t, next->second)); rec.erase(next);
            }
            else rec.insert(MP(t, t));
        }
        else {
            pos--;
            r = pos->second;
            if (r < t)  printf("%d ", t);
            else if (r >= t) {
                printf("%d ", r + 1);
                t = r + 1;
            }
            // 看下是否要合并
            if (t == pos->second + 1 && org->first == t + 1){

                pos->second = org->second; 
                rec.erase(org);
            }
            else if (t == pos->second + 1) pos->second += 1;
            else if (org->first == t + 1){
                rec.insert(MP(t, org->second)); rec.erase(org);
            }
            else rec.insert(MP(t, t));
        }
        for (auto & el: rec) printf("(%d, %d)", el.first, el.second);

    }
    return 0;
}

法2：

并查集：去维护一段连续的区间，每棵树的根就是这段区间右边第一个没用过的点。所以每个fa[]都存右边第一个数就好了。
fa[]存右边第一个数。
find()找到右边第一个没用过的点就是这棵树的根，因为fa[]存的都是右边的点，所以就和题意一样往右不断地找。但是用到路径压缩，后面查找会更快。
算法流程：
一开始所有数都没用过，fa[]像并查集一样都初始化为-1，或者自身。
找到x自身往右包括自身第一个没用过的点u，然后u这个点就被用过了：fa[u]=u+1，方便下次find。

int find(int x){
    if (fa[x] == -1) return x;
    return fa[x] = find(fa[x]);
}

int main(void){
    cin >> n;
    memset(fa, -1, sizeof(fa));
    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        int t = find(x);
        printf("%d ", t);
        fa[t] = t + 1; 
    }
    return 0;
}