蓝桥杯2019年第十届真题-修改数组-题解（C++代码）

解题思路：用并查集思路，如果一个数的父节点就是当前数的位置，如果标记下一个数值一样的数的位置+1

#include<bits/stdc++.h>
#define x first
#define y second
#define mem1(h) memset(h,-1,sizeof h)
#define mem0(h) memset(h,0,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
//#############以上是自定义技巧（可忽略）########## 
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e9+7,P=131;
int n;
int fa[N];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
    cin>>n;
    for(int i=0;i<=n;i++)fa[i]=i;
    for(int x,i=1;i<=n;i++){
        scanf("%d",&x);
        x=find(x);
        printf("%d ",x);
        fa[x]=x+1;
    }
    return 0;
}