自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 22:54:02，当前版本为作者最后更新于2023-12-07 23:10:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们首先分析一下题目给出的操作。

对于某个元素 $a_i$，如果序列 $a$ 中存在另一个元素 $a_p$ 满足 $a_i=a_p$，那么显然，去掉 $a_i$ 后的序列 $a$ 的 $\operatorname{mex}$ 和原本的序列 $a$ 的 $\operatorname{mex}$ 相等，所以操作后，$a_i$ 会变成原本的序列 $a$ 的 $\operatorname{mex}$。

同时，对于某个元素 $a_j$，若其满足 $a_j$ 大于原本的序列 $a$ 的 $\operatorname{mex}$，那么显然，是否去掉 $a_j$ 对序列 $a$ 的 $\operatorname{mex}$ 没有影响，所以操作后，$a_j$ 也会变成原本的序列 $a$ 的 $\operatorname{mex}$。

我们再来考虑，对于某个元素 $a_k$，若其满足：

• 序列 $a$ 中不存在另一个元素 $a_p$ 满足 $a_k=a_p$；
• $a_k$ 小于原本序列 $a$ 的 $\operatorname{mex}$；

那么，去掉 $a_k$ 之后，序列 $a$ 的 $\operatorname{mex}$ 就会变成 $a_k$，所以操作前后，$a_k$ 的值不变。

于是我们明白了操作前后序列 $a$ 的变化。可以用桶维护，做到以 $\mathcal O(n)$ 的复杂度进行一次操作，那么对于 $m=1$ 的情况，我们直接模拟即可。

我们继续分析。

我们先进行第一次操作，把所有满足序列 $a$ 中存在另一个元素与其相等或其大于序列 $a$ 的 $\operatorname{mex}$ 的元素的值都修改为序列 $a$ 的 $\operatorname{mex}$。

然后我们再进行第二次操作，内容和第一次操作相同。

于是容易证明，此时的序列 $a$ 除最大值外，剩余的元素都满足不存在另一个元素 $a_p$ 与其相等，而且最大值要么等于序列 $a$ 的 $\operatorname{mex}$ 的值加一，要么等于序列 $a$ 的 $\operatorname{mex}$ 的值减一。

我们设序列 $a$ 中的最大值为 $x$。根据我们之前分析的内容，若序列 $a$ 中只有一个元素的值为 $x$，则 $x$ 的值不会再改变；若序列 $a$ 中有多个元素的值为 $x$，我们分两类讨论：

• 若 $x+1$ 等于序列 $a$ 的 $\operatorname{mex}$，则所有值等于 $x$ 的元素的值都会变为 $x+1$，此时新的序列 $a$ 的 $\operatorname{mex}$ 为 $x$；
• 若 $x-1$ 等于序列 $a$ 的 $\operatorname{mex}$，则所有值等于 $x$ 的元素的值都会变为 $x-1$，此时新的序列 $a$ 的 $\operatorname{mex}$ 为 $x$。

可以发现，若序列 $a$ 中有多个元素的值为 $x$，则进行多次操作时，$x$ 的值在一直循环，不断加一、减一，每两次操作的效果可以抵消，于是可以得到：

• 当 $m$ 为偶数时，进行 $m$ 次操作后的序列 $a$ 与进行 $2$ 次操作后的序列 $a$ 相同；
• 当 $m$ 为奇数且 $m\ne 1$ 时，进行 $m$ 次操作后的序列 $a$ 与进行 $3$ 次操作后的序列 $a$ 相同。

那我们直接根据此模拟即可。

#include <bits/stdc++.h>

using namespace std;
const int N=1e6+5;
int n,m,a[N],cnt[N];
void work(){
	int res=0;
	for(int i=0;i<=n;i++) cnt[i]=0;
	for(int i=1;i<=n;i++) if(a[i]<=n) cnt[a[i]]++;
	for(int i=n;i>=0;i--) if(cnt[i]==0) res=i;
	for(int i=1;i<=n;i++) if(a[i]>res||cnt[a[i]]>1) a[i]=res;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	work();
	if(m!=1){
		work();
		if(m%2==1) work();
	}
	for(int i=1;i<=n;i++) cout<<a[i]<<(i==n?'\n':' ');
}
signed main(){
	ios::sync_with_stdio(0);
	int T=1;
	cin>>T;
	while(T--) solve();
	return 0;
}