题目链接

https://www.dotcpp.com/oj/problem2301.html

解题思路

确实有点难理解。
从简单的讲起：
有这么一个思路，把已经被出现过的数构成的不连续的几段区间记录下来，比如用过了1，2，5，6，7，9，那么我们就记录下来区间[1,2]，[5,7]，[9,9]。判断当前数在不在任意一个区间里，若在，那就要找到他所在区间右端点的右边一个位置，比如，要修改的数为6，显然6已经出现过了，因此，我们要把6修改成区间右端点7的后一个，即为8。这样之后又出现一个问题，5，6，7，8，9，齐活了，可以合并区间了，[5,7]，[8,8]，[9,9]合并为[5,9]。比如，要修改的数为3，因为3并没有出现过，因此我们直接把3添加进去就行。
你要吐槽，为啥这么麻烦，又是存区间又是插入又是合并区间的，太麻烦了。
确实麻烦，但是也确实可以实现，这是 yxc大神的讲解，第一个好像就是 。
所以这里提供了一种思路难但是实现简单的方法：
并查集。（太巧妙了）
没想到吧，是的，并查集。
你想想其实一个已经出现过的区间，不就是一个连通的区域嘛，我们让每个连通区域的根都保持在未出现过的数上，所以每次遍历到的数如果属于某个连通区域，那我们就让这个数直接修改成根即可，再把连通区域的根修改成未出现过的数。
还是上面的例子，连通区域(1,2)的根为3，(5,6,7)的根为8，(9)的根为10，若插入8，连通区域(5,6,7)的根就要变成比8还大的数，因为8此时出现了，所以需要修改根为9，但是9也出现了，所以要修改为10，10没出现，就是10了没问题。同时，8对应的根也要修改为与其连通的区域的根，即10，至此，(5~9)构成一个连通区域，根为10。

AC代码

#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d ",x)
using namespace std;
const int N=1e5+10;
int fa[N],x,n;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    sc(n);
    for(int i=1;i<=N;i++) fa[i]=i;//初始化，每个数就是一个点，我们要做的初始化就是每个点的根都为自己
    for(int i=1;i<=n;i++) {
        sc(x);
        x=find(x);//每输入一个数，直接找到它的根
        pr(x);//因为它的根是未出现过的，所以直接输出就行，也就意味着输入的x被修改成了它的根
        fa[x]=x+1;//此时输入的x的根也出现过了，所以我们得刷新x所在的连通区域的根，刷新为x+1，即区间右端点的右边一个数（这样是不是比较形象）。同时，这还解决了区间合并的问题，就算x+1出现过，find函数中的路径压缩也会使两个连通区域合并，最终同根。
    }
}