题解

题目要求构造一个长度为 $n$ 的数组 $b$，使得对于每个前缀 $i$，给定的 $a_i$ 都必须是该前缀的众数之一。这里众数定义为出现次数最多的正整数，若有多个则任一均可。

核心思路

如果我们能构造出所有元素互不相同的数组 $b$，那么任意前缀中每个数出现次数均为 $1$，所有出现的数都是众数。此时只要保证 $a_i$ 在 $b_1 \dots b_i$ 中出现过，它自然就成为众数。
因此，问题转化为：构造一个 $1 \sim n$ 的排列（部分数字可以缺失，但 $b$ 长度恰为 $n$，使用 $1 \sim n$ 中未出现的数字补齐，使得所有元素依然互异），并满足每个 $a_i$ 都在其前缀中出现至少一次。

对于每个 $a_i$，若它是在 $a$ 中第一次出现，我们就在 $b_i$ 放置 $a_i$；否则，$a_i$ 已经在前面的某个位置被放入了 $b$，当前 $b_i$ 可以填入任意一个未在 $a$ 中出现的数字，以避免重复。这样可以保证：

• 所有放入的 $a_i$ 首次出现值互不相同；
• 用来填充的数字均从未在 $a$ 中出现过，它们之间互不相同，也不会与任何 $a_i$ 的首次出现值重复。

由此构造出的 $b$ 所有元素互异。

算法步骤

1. 读入 $n$ 和数组 $a$。初始化一个大小为 $n+1$ 的标记数组（或布尔数组）seen，记录哪些数值已在 $a$ 中出现过。同时准备一个长度为 $n$ 的数组 $b$，初始值全为 $0$。
2. 遍历 $i$ 从 $0$ 到 $n-1$：
   • 令 $x = a_i$。
   • 若 seen[x] 为假，说明 $x$ 第一次出现，则令 $b_i = x$，并设 seen[x] = true。
   • 否则，$b_i$ 保持 $0$（表示待填充）。
3. 收集所有未在 $a$ 中出现过的数字（即 seen[i] == false 的 $i$，$1 \le i \le n$），放入一个队列 $q$。
4. 再次遍历 $b$，若 $b_i = 0$，则从 $q$ 队首取出一个数字填入，并弹出队首。
5. 输出 $b$ 数组。

正确性证明

• 由步骤2，每个 $a_i$ 的首次出现值都被直接放入 $b$。对于后续重复出现的 $a_i$，该值一定已经存在于 $b$ 的前缀中（位于某个 $j < i$ 的位置）。因此对任意前缀 $i$，$a_i$ 至少出现一次。
• 所有被填入的数字分为两类：首次出现的 $a$ 值（互异），以及未在 $a$ 中出现过的数字（互异，且与第一类不交）。因此 $b$ 中所有元素互异。
• 在互异的前提下，任何前缀里每个元素频率均为 $1$，故任意出现的元素都是众数。特别地，$a_i$ 出现在前缀中，所以它一定是众数之一。

时间复杂度

每组测试数据只需两次遍历，时间复杂度 $O(n)$。所有测试数据 $\sum n \le 2 \cdot 10^5$，完全可以在时限内运行。

C++ 代码（依据标程）

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--)
    {
        int n;
        cin >> n;
        vector<int> a(n + 1), b(n);
        for (int i = 0; i < n; i++)
        {
            int x;
            cin >> x;
            if (!a[x])
            {
                b[i] = x;
                a[x] = 1;
            }
        }
        queue<int> q;
        for (int i = 1; i <= n; i++)
            if (!a[i])
                q.push(i);
        for (int i = 0; i < n; i++)
        {
            if (!b[i])
            {
                b[i] = q.front();
                q.pop();
            }
        }
        for (int i = 0; i < n; i++)
            cout << b[i] << " \n"[i == n - 1];
    }
    return 0;
}