Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)（我们可以使用这个数学归纳法，得到一个关于 a 的一个关键性质）（我们还是没有想到怎么做？那应该是对 a 的性质探索的还不够多） · znzryb
## 题目大意
**题目描述**
定义集合 $S$ 的 $k$-mex 为未在 $S$ 中出现的第 $k$ 小的非负整数。例如，集合 $[1, 2, 1]$ 的 $1$-mex 是 $0$，$2$-mex 是 $3$。
给定一个长度为 $n$ 的非负整数数组 $a_1, a_2, \ldots, a_n$。你需要判断是否存在一个非负整数数组 $b_1, b_2, \ldots, b_n$（其中 $0 \le b_i \le 10^9$），使得对于所有 $1 \le i \le n$，前缀 $[b_1, \ldots, b_i]$ 的 $(n-i+1)$-mex 恰好等于 $a_i$。
如果存在这样的数组，请构造并输出任意一个满足条件的数组 $b$；如果不存在，请报告无解。
**输入格式**
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
**输出格式**
对于每个测试用例，如果存在满足条件的数组 $b$，第一行输出 `YES`（不区分大小写），第二行输出 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i \le 10^9$）。
如果不存在，仅输出一行 `NO`。
**样例数据**
```
Input:
6
3
3 3 1
3
2 1 3
1
0
1
2
4
7 5 2 2
6
6 6 6 4 3 3
Output:
YES
2 0 2
NO
YES
67
NO
NO
YES
5 2 1 5 2 0
```
**样例解释**
在第一组测试用例中，$a = [3, 3, 1]$。我们可以验证数组 $b = [2, 0, 2]$ 满足条件：
- 当 $i=1$ 时，需要计算前缀 $[b_1] = [2]$ 的 $(3-1+1)$ 即 $3$-mex。未在数组中出现的非负整数依次为 $0, 1, 3, 4, \dots$，其中第 $3$ 小的是 $3$，等于 $a_1$。
- 当 $i=2$ 时，需要计算前缀 $[b_1, b_2] = [2, 0]$ 的 $(3-2+1)$ 即 $2$-mex。未在数组中出现的非负整数依次为 $1, 3, 4, \dots$，其中第 $2$ 小的是 $3$，等于 $a_2$。
- 当 $i=3$ 时，需要计算前缀 $[b_1, b_2, b_3] = [2, 0, 2]$ 的 $(3-3+1)$ 即 $1$-mex。未在数组中出现的非负整数依次为 $1, 3, 4, \dots$，其中第 $1$ 小的是 $1$，等于 $a_3$。
在第二组测试用例中，$a = [2, 1, 3]$。可以证明不存在任何满足条件的数组 $b$，因此输出 `NO`。
在第三组测试用例中，$a = [0]$。构造 $b = [67]$ 满足条件，因为前缀 $[b_1] = [67]$ 的 $1$-mex 是 $0$，恰好等于 $a_1$。
## 思路讲解
::: 如何解决这道题目的难点，即所谓的后效性，构造前面的可能影响后面的
你在问的是：
你并不关心那种“当前选了 `b_i` 会不会把未来某个 `a_j` 自己的位置占掉”的浅层冲突，因为你认为这个很简单、不是难点。
你真正关心的是更深层的后效性耦合：某些位置的 `a_j` 要想合法，依赖于前面若干步对 `b` 的构造结果（也就是前面是否保留了足够且合适的缺失结构、是否在合适区间内消耗了哪些值）。
换句话说，你的问题是：如何处理这种“未来可行性依赖前面资源分配”的深层耦合，而不是只处理“值被提前占用”这一类显然冲突。
---
你这个“更深耦合”说得对，真正难点是这个，不是“占坑”。
我直接讲这层耦合本质：
- 设 `used(<x)` 表示当前前缀里，`0..x-1` 中已经被你“用掉（出现过）”的不同值个数。
- 那么 `missing(<x) = x - used(<x)`。
- 题目在第 `i` 步其实要求的是`missing(<a_i) = n-i`，等价于`used(<a_i) = a_i-(n-i)`。
这就出现了你说的深耦合：
你现在选一个值 `v` 放进 `b_i`，会让 `used(<x)` 对所有 `x>v` 都 `+1`。
也就是一次选择会“联动影响很多阈值”，不是只影响当前 `a_i`。
---
怎么解这个后效性？
关键是把它看成“资源分配”：
- 每次当你发现当前 `used(<a_i)` 还差 1，你就**必须**消耗一个 `<a_i` 的资源值。
- 这个资源值选小了，会影响更多未来阈值；选大了，只影响较大的阈值。
- 所以为了给未来留最大余地，策略是：**在所有可选的** **`<a_i`** **资源里，选最大的那个。**
这一步就是你要的“解决深层后效性”的核心贪心，不是拍脑袋，直觉上是“最小扰动”：
- 选更小的 `v` 会额外改动一批中小阈值（`v < x <= v'` 这段）；
- 选更大的 `v'` 不会多改任何阈值，改动范围更窄；
- 所以“选最大可行值”始终更保守，未来选择空间更大。
---
你可以把整题理解成两类约束同时满足：
1. **硬约束**：当前步 `used(<a_i)` 必须达到目标值。
1. **耦合控制**：当必须加 1 时，把这 `+1` 尽量放在“最高位置”上，减少对小阈值链条的污染。
---
一句话总结你问的点：
这题的深层后效性来自“一个 `b_i` 对多阈值前缀计数的联动”，而破解方式是“把每次必做增量放到最大可行值上”，把全局耦合压成局部可维护贪心。
你如果愿意，我下一条只讲“这个贪心为什么可以交换论证成立”，不讲实现。
:::
首先，需要这样子想，每一个 a 代表什么？可以这样子想：
不难发现：（使用归纳法）
当然，我们可以换成这个 i。
为什么可以 = 呢？
其实这个规律还是没有那么难以观察出来的，毕竟**这个 a1 代表第 n 个空，a2 代表第 n-1 个空，你也很难想象第 n-1 个空在第 n 个空后面是吧**？
::: AI 使用这个 EDF（Earliest deadline first scheduling） 调度，即我们都学过的，选择结束时间最靠前的这个任务，想出了这道题目的解法
好，我前面的论证确实有问题——"影响范围小所以更安全"本质上是在循环论证，没说清楚"为什么更安全"。换一个角度重新讲。
每个值 $v$ 有一个"存活期限"：因为 $a$ 非递增，迟早 $a$ 会降到 $\le v$，那之后 $v$ 就再也不满足 $v < a_j$ 了，永远用不上了。$v$ 越大，这个期限越早到来。
所以问题变成了：你手里有一堆资源，每个资源有一个"过期时间"，大值过期早，小值过期晚。每步最多用一个。目标是按需及时消耗。
这就是经典的"最早截止时间优先"（EDF）调度：永远先用快过期的那个。原因也不是什么"影响范围"，而是——**快过期的你现在不用，以后就用不了了；晚过期的你现在不用，以后还能用。** 所以先用快过期的不会错过任何机会，反过来先用晚过期的可能让快过期的白白浪费。
这个逻辑成立的前提就是 $a$ 非递增：它让大值的"过期时间"比小值早，形成了一个单调的截止时间序列。如果 $a$ 不单调，大值可能在未来某步又"复活"了（$a$ 重新变大），截止时间就不是单调的了，EDF 的前提就崩了。
:::
~~我觉得上面 AI 的这个角度还是挺好的，但是我其实觉得稍微有点扯。~~
然后我们还是没有想到怎么做？那应该是对 a 的性质探索的还不够多！（继续沿着探索 a 的性质的这条路走）
其实光有这个递减性质，其实还是不够的，我们不妨多探索一些性质，比如说 ai+1 其取值范围到底是在哪里？
通过上面的推导，我们不难得出如下结论：
这道题目，我们的做法需要用到 dsu on next 技巧。那么要注意这个合并方向。
```cpp
vector<ll> B(N + 2);
ll cur;
vector<ll> wp;
ll top_b = 0;
for (int i = 1; i <= N; ++i) {
// 我觉得一般来说，你还是不要用哨兵节点，老老实实特判比较好，确保初值正确
if (i == 1) {
if (A[i] > N) {
cout << "NO\n";
return;
}
if (A[i] == N) {
wp.push_back(i);
cur = N;
} else if (A[i] == N - 1) {
B[i] = mod;
cur = N - 1;
} else {
cout << "NO\n";
return;
}
merge(A[i], A[i] - 1);
continue;
}
if (A[i] == cur) {
// wp 存储的就是我们存下来的，等待填充的 B 数组中的位置
wp.push_back(i);
} else {
ll fcur = find(cur);
if (fcur < A[i]) {
cout << "NO\n";
return;
}
// 之所以要 merge A[i] 和 A[i-1]，是因为 A[i] 是一个空，也不要填充 b 了。
merge(A[i], A[i] - 1);
for (ll j = fcur; j > A[i]; --j) {
merge(j, j - 1);
if (wp.empty()) {
cout << "NO\n";
return;
}
B[wp.back()] = j;
wp.pop_back();
}
cur = A[i];
B[i] = mod;
}
}
while (!wp.empty()) {
if (!merge(top_b, top_b - 1)) {
cout << "NO\n";
return;
}
B[wp.back()] = top_b;
wp.pop_back();
top_b++;
}
cout << "YES\n";
for (int i=1;i<=N;++i) {
cout<<B[i]<<" ";
}
```
## AC代码
AC
[https://codeforces.com/contest/2207/submission/367198322](https://codeforces.com/contest/2207/submission/367198322)
::: 源代码
```cpp
/**
* Problem: E1. N-MEX (Constructive Version)
* Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2207/problem/E1
* Created: 2026-03-14 18:34:09
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT, testcase;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<ll> A(N + 2);
for (int i = 1; i <= N; ++i) {
cin >> A[i];
}
if (!is_sorted(A.begin() + 1, A.begin() + N + 1, greater<>())) {
cout << "NO\n";
return;
}
map<ll, ll> fa;
auto find = [&](ll x) {
ll root = x;
while (fa.contains(root)) {
root = fa[root];
}
// 写两遍，这一遍进行路径压缩
while (x != root) {
tie(x, fa[x]) = make_tuple(fa[x], root);
}
return root;
};
auto merge = [&](ll x, ll y) -> bool {
x = find(x), y = find(y);
if (x == y) return false;
fa[x] = y;
return true;
};
// for (int i = 1; i <= N; ++i) {
// merge(A[i], A[i] - 1);
// }
// merge(N, N - 1);
// ll mx = fa.begin()->first;
vector<ll> B(N + 2);
ll cur;
// A[0] = N;
// ll rem_b = 0;
vector<ll> wp;
ll top_b = 0;
for (int i = 1; i <= N; ++i) {
if (i == 1) {
if (A[i] > N) {
cout << "NO\n";
return;
}
if (A[i] == N) {
// rem_b++;
wp.push_back(i);
cur = N;
} else if (A[i] == N - 1) {
// B.push_back(mod);
B[i] = mod;
cur = N - 1;
} else {
cout << "NO\n";
return;
}
merge(A[i], A[i] - 1);
continue;
}
if (A[i] == cur) {
// rem_b++;
wp.push_back(i);
} else {
// B[i] = mod;
ll fcur = find(cur);
if (fcur < A[i]) {
cout << "NO\n";
return;
}
merge(A[i], A[i] - 1);
for (ll j = fcur; j > A[i]; --j) {
merge(j, j - 1);
// B.push_back(j);
// rem_b--;
if (wp.empty()) {
cout << "NO\n";
return;
}
B[wp.back()] = j;
wp.pop_back();
}
cur = A[i];
B[i] = mod;
// if (rem_b < 0) {
//
// }
// while (rem_b > 0) {
// rem_b--;
// if (!merge(top_b, top_b - 1)) {
// cout << "NO\n";
// return;
// }
// B.push_back(top_b);
// top_b++;
// }
// B.push_back(mod);
}
}
while (/*rem_b > 0*/ !wp.empty()) {
// rem_b--;
if (!merge(top_b, top_b - 1)) {
cout << "NO\n";
return;
}
B[wp.back()] = top_b;
wp.pop_back();
// B.push_back(top_b);
top_b++;
}
// if (rem_b < 0) {
// cout << "NO\n";
// return;
// }
cout << "YES\n";
for (int i=1;i<=N;++i) {
cout<<B[i]<<" ";
}
// for (auto b: B) {
// cout << b << " ";
// }
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2207/submission/367198322
1
3
3 3 1
1
1
0
1
6
6 6 6 4 3 3
*/
```
:::
## 心路历程（WA，TLE，MLE……）
对拍拍出来的数据。
```cpp
1
4
4 4 3 1
```
::: brute
```cpp
/**
* Problem: E1. N-MEX (Constructive Version)
* Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2207/problem/E1
* Created: 2026-03-18 13:50:55
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT, testcase;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<ll> A(N + 2);
for (int i = 1; i <= N; ++i) {
cin >> A[i];
}
vector<ll> sts;
for (int i = 0; i <= N; ++i) {
sts.push_back(i);
}
bool ok = false;
auto dfs = [&](auto &&go, vector<ll> st, vector<ll> B, ll idx) -> void {
if (ok) {
return;
}
if (idx == 0) {
ok = true;
// #ifdef LOCAL
// debug1d(B);
// #endif
return;
}
vector<ll> back_up = st;
for (int i = 0; i <= N + 1; ++i) {
if (binary_search(all(st), i)) {
auto it = lower_bound(all(st), i);
st.erase(it);
}
B.push_back(i);
if (idx - 1 < SZ(st) && st[idx - 1] == A[N - idx + 1]) {
// #ifdef LOCAL
// debug1d(st);
// debug(idx);
// debug(st[idx-1])
// #endif
go(go, st, B, idx - 1);
}
B.pop_back();
st = back_up;
}
};
dfs(dfs, sts, {}, N);
if (ok) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
*/
```
:::
::: gen
```cpp
/**
* Problem: E1. N-MEX (Constructive Version)
* Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2207/problem/E1
* Created: 2026-03-18 13:51:07
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
// ll N;
// cin >> N;
cout<<1<<"\n";
ll N=uniform_int_distribution<ll>(1,7)(rng);
cout<<N<<"\n";
for (int i=1;i<=N;++i) {
cout<<uniform_int_distribution<ll>(0,N)(rng)<<" ";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::