AcWing 1242. 修改数组
给定一个长度为 N 的数组 A=[A1,A2,???AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。
小明会依次修改 A2,A3,???,AN。
当修改 Ai 时，小明会检查 Ai 是否在 A1?Ai?1 中出现过。
如果出现过，则小明会给 Ai 加上 1；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1，直到 Ai 没有在 A1?Ai?1 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。
现在给定初始的 A 数组，请你计算出最终的 A 数组。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,???,AN。
输出格式
输出 N 个整数，依次是最终的 A1,A2,???,AN。
数据范围
1≤N≤105,
1≤Ai≤106
输入样例：
5
2 1 1 3 4
输出样例：
2 1 3 4 5
难度： 中等
时/空限制： 1s / 64MB
总通过数： 578
总尝试数： 1596
来源： 第十届蓝桥杯省赛C++A/研究生组,第十届蓝桥杯省赛JAVAA/研究生组
算法标签
这道题我刚开始用的是线段树，但是我还是太菜菜了，可能我写的不是最优的线段树，然后代码如下：
#include<iostream>using namespace std;const int N=1e5+10;struct Node
{
int l,r;bool st;
} tr[N*4];
int op=5;
bool check[N];
int a[N];void pushup(int u)
{
if(tr[u<<1].st&&tr[u<<1|1].st)tr[u].st=true;
}void build(int u,int l,int r)
{
tr[u]={
l,r,false};if(l==r) return;int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);
}void modify(int u,int x)
{
if(tr[u].l==x&&tr[u].r==x) tr[u].st=true;else if(tr[u].l!=tr[u].r){
int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x);if(x>mid) modify(u<<1|1,x);pushup(u);}
}bool query(int u,int t)
{
if(tr[u].l==tr[u].r&&tr[u].l>t&&tr[u].st==false) {
op=tr[u].l;return true;}else if(tr[u].l==tr[u].r) return false;int mid=tr[u].l+tr[u].r>>1;if(query(u<<1,t)) return true;else if(query(u<<1|1,t)) return true;return false;
}int main(void)
{
int n;cin>>n;build(1,1,N);for(int i=1;i<=n;i++){
int t;cin>>t;if(!check[t])modify(1,t),a[i]=t,check[t]=true;else{
query(1,t);modify(1,op);check[op]=true;a[i]=op;}}for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}可能在query方面错了，然后我就去看y总的视频
y总的方法从来没有让我失望过，真的太强了
用并查集的方法，p[i]表示i这个点可以选取的值。
这里是另类的单链表式的并查集。
最后，代码如下：
#include<iostream>using namespace std;const int N=2e6+10;int p[N];
int a[N];int find(int x)
{
if(p[x]!=x) return p[x]=find(p[x]);return x;
}int main(void)
{
for(int i=1;i<N;i++) p[i]=i;int n;cin>>n;for(int i=1;i<=n;i++){
int x;scanf("%d", &x);x = find(x);printf("%d ", x);p[x] = x + 1;}
}