题解：CF2207E1 N-MEX (Constructive Version)

MaxBlazeResFire · 2026-03-10 12:38:59 · 题解

不难想到 a_i\geq a_{i+1}，当 a_i>a_{i+1} 时，说明有一个任意的不在当前 \rm mex 集合内的数被添加；当 a_i=a_{i+1} 时，恰有一个当前 \rm mex 集合内的数被添加。\rm mex 集合为整体未出现数集合的 \leq a_i 的那部分子集。

注意为了满足 a_{i}>a_{i+1} 的所有条件，需要使得所有 [a_i,a_{i+1}) 内的数都在之前出现过。开个数组维护一下每个数最早需要放置的时间，每次取要求最严格的放即可。实际上取最大的放即可。

实现起来，维护 S 表示小于等于当前 a_i 的 \rm mex 集合，时刻注意不能往里加入后面有的 a_i。当 a_i=a_{i-1} 时，从 S 中取最大的元素设置，否则随便设置一个即可。O(n\log n)。

容易单指针做到线性。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 200005

int n,a[MAXN],b[MAXN],vis[MAXN];

inline void clear(){
    for( int i = 0 ; i <= n + 1 ; i ++ ) a[i] = b[i] = vis[i] = 0;
}

inline void solve(){
    scanf("%lld",&n);
    for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&a[i]),a[i] <= n ? vis[a[i]] ++ : 0;
    if( a[1] != n && a[1] != n - 1 ){ puts("NO"); clear(); return; }
    a[0] = b[0] = n;
    for( int i = n - 1 ; i >= 0 ; i -- )
        if( a[i] < a[i + 1] ){ puts("NO"); clear(); return; }
    //S 维护 >a[i] 的 mex 集合
    set<int> S;
    for( int i = 0 ; i <= n ; i ++ ) if( !vis[i] ) S.insert( i );
    for( int i = 1 ; i <= n ; i ++ ){
        if( i == 1 || a[i] == a[i - 1] ){
            if( !(int)S.size() ){ puts("NO"); clear(); return; }
            b[i] = *S.rbegin(),S.erase( b[i] );
        }
        else{
            b[i] = a[i] + 2;
        }
    }
    for( int i = 0 ; i <= n + 1 ; i ++ ) vis[i] = 0;
    for( int i = 1 ; i <= n ; i ++ ) vis[b[i]] ++;
    int mex = 0; while( vis[mex] ) mex ++;
    for( int i = n ; i >= 1 ; i -- ){
        if( mex != a[i] ){ puts("NO"); clear(); return; }
        vis[b[i]] --;
        if( vis[b[i]] || b[i] > mex )
            mex ++; while( vis[mex] ) mex ++;
    }
    puts("YES");
    for( int i = 1 ; i <= n ; i ++ ) printf("%lld ",b[i]);
    puts("");
    clear();
}

signed main(){
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}