并查集。。。。。。

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e6+10;

int p[N];

int n;

int find(int x)

{

if(p[x]!=x)p[x]=find(p[x]);

return p[x];

}

int main()

{

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n;

    int a;

    for(int i=1;i<=N;++i)p[i]=i;

    for(int i=1;i<=n;++i)

    {

      cin>>a;

      a= find(a);

      cout<<a<<" ";

      p[a]=a+1;//把a接到比自己大一的结点上,下次在碰到a直接输出a+1

               //注意find()函数有路径压缩,如已有2,3,4,5,经过路径压缩它们全部接到6,下次再碰到它们其中一个直接输出6

    }

    return 0;

}