算法1

区间合并、查找

将每次询问的值加入区间中并进行不断的合并，询问。因为每次询问的值可能在已知区间内，所有要注意upper_bound求的时候要加入{x,inf}，这个根据不同情况分析，坑了我好久。。。

C++ 代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#define ll long long
using namespace std;

int n;
const int maxn=1e5+5, inf=1<<30;
int a[maxn];
set<pair<int,int>> s;

void add(int x){
    auto p2=s.upper_bound({x,inf});
    auto p1=p2;
    p1--;
    if(p2->first-p1->second==2){
        s.erase(p1);
        s.erase(p2);
        s.insert({p1->first,p2->second});
    }
    else{
        if(x-1<=p1->second){
            s.erase(p1);
            s.insert({p1->first,p1->second+1});
        }
        else if(x+1==p2->first){
            s.erase(p2);
            s.insert({p2->first-1,p2->second});
        }
        else{
            s.insert({x,x});
        }
    }
}

int get(int x){
    auto t=s.upper_bound({x,inf});
    t--;
    if(t->second>=x) return t->second+1;
    return x;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    s.insert({-inf,-inf});
    s.insert({inf,inf});
    for(int i=0;i<n;i++){
        int t=a[i];
        a[i]=get(a[i]);
        add(t);
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";

    return 0;
}

算法2

并查集

用并查集做简直秒杀。。。直接记录每个点的下一个位置就好了。

C++ 代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#define ll long long
using namespace std;

int n;
const int maxn=1e5+5, inf=1<<30;
int a[maxn], f[1000000+5];

int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<1000000+5;i++){
        f[i]=i;
    }
    for(int i=0;i<n;i++){
        int p1=find(a[i]);
        a[i]=p1;
        int p2=find(p1+1);
        f[p1]=p2;
    }

    for(int i=0;i<n;i++) cout<<a[i]<<" ";

    return 0;
}