传送门：洛谷 Harder Problem | Codeforces D. Harder Problem

更佳的阅读体验：CF2044D 题解

简要题意：给定序列 $a$，尝试构造一个序列 $b$，使得 $a$ 中每个元素 $a_i$ 都是 $b$ 中前 $i$ 个数构成的序列的众数（mode），且 $b$ 中每个元素 $b_i$ 都满足 $b_i \in [1, n]$。

由众数的定义，可以想到一个序列中可以有多个众数，所以当 $[1, n]$ 中的每个数都各出现一次时，每个数都是序列 $b$ 的众数。

此时，问题转化为构造一个 $[1, n]$ 的排列。

要保证 $a$ 中每个元素 $a_i$ 都是 $b$ 中前 $i$ 个数构成的序列的众数，只需要在 $a_i$ 第一次出现的位置输出 $a_i$，其余的位置输出任意一个 $a$ 中没有出现过的数即可。

#include <iostream>
#include <bitset>
using namespace std;

const int N = 2e5 + 10;
int t, n, a[N], ans[N];
bitset<N> vis;
basic_string<int> num, inum;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        num.clear(), inum.clear(), vis.reset();
        fill(ans + 1, ans + n + 1, 0);
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i], vis.set(a[i]);
        for (int i = 1; i <= n; ++i) {
            if (vis[i]) num += i;
            else inum += i;
        } vis.reset();
        int pos = 0;
        for (int i = 1; i <= n; ++i) {
            if (!vis[a[i]]) vis.set(a[i]), ans[i] = a[i];
            else ans[i] = inum[pos++];
        } for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
    } return 0;
}