自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:46:16，当前版本为作者最后更新于2023-04-05 20:02:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先特判 $k=0$ 的情况，此时的答案为非 $0$ 数的个数，改法是将它们全改成 $0$。

再特判 $k$ 较大的情况，此时的答案为 $0$。

否则，对于 $k$ 大小适中的情况，我们从前往后遍历数组，同时维护当前区间的 $\operatorname{mex}$ 值。根据 $\operatorname{mex}$ 的定义，显然对于左端点相同的区间，右端点不断右移的过程中 $\operatorname{mex}$ 单调不降。因此，如果 $\operatorname{mex}$ 值在某一时刻超过了 $k$（一定是遍历到一个 $k$ 导致的），则继续右移是没有意义的，此时清空维护的区间。如果 $\operatorname{mex}$ 值在某一时刻等于 $k$，则将此时区间右端点改为 $k$。

时间复杂度 $\mathcal O(n)$。

$k=0$ 或 $k$ 较大的正确性是显然的，下面证明上述 $k$ 适中贪心算法的正确性。

引理一：存在一种最优方案，使得所有修改的位置都被改为 $k$。

证明：考虑任意一种最优方案，如果一个位置被修改，使得不存在 $\operatorname{mex}$ 为 $k$ 的区间，则将它改为 $k$ 也不存在。原因是包含 $k$ 的区间的 $\operatorname{mex}$ 一定不等于 $k$，而从这个位置将数列分开，根据方案合法性，剩余的部分的 $\operatorname{mex}$ 也一定不是 $k$。$\square$

因此，我们只需要考虑将所有修改的位置都改为 $k$ 的情况。

同样的理由，我们不需要考虑原数列中包含 $k$ 的连续子段，因此可以将原数列按照 $a_i=k$ 的位置分为若干段，每一段都不包含 $k$。另外，显而易见地，大于 $k$ 的 $a_i$ 没有意义。综上，只要我们解决了子任务三（保证 $a_i < k$），原问题得解。

在子任务三中，一段区间的 $\operatorname{mex}$ 等于 $k$，当且仅当这段区间包含 $0\sim k-1$ 的所有数。我们找到最靠左的这样的区间，则这段区间内至少要有一个数被改为 $k$。在改为 $k$ 后，从被修改的位置往右是一个子问题。

引理二：存在一种最优方案，使得所有被修改的位置都是上述区间的右端点。

证明：考虑任意一种最优方案，假设一次修改没有改右端点，则改右端点一定不劣。原因是这样可以尽量缩减问题的规模，由于 $\operatorname{mex}$ 有单调性，这么操作并不会使得下一个修改位置提前，只可能使得下一个修改位置延后。$\square$

子任务三的贪心算法正确性得证。根据上述推理，原问题的贪心算法正确性得证。

代码：

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
	uniform_int_distribution<int> dist(L, R);
	return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const int N = 1e6+5;

int n, k, a[N], b[N], cnt[N], mex, ans;

int read() {
	int x = 0, k = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') k *= -1;
	for(; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * k;
}

void write(int x, char end = 0) {
	if(x < 0) putchar('-'), x = -x;
	if(x < 10) putchar(x ^ 48);
	else {
		write(x / 10);
		putchar((x % 10) ^ 48);
	}
	if(end) putchar(end);
}

int main() {
	n = read(); k = read();
	rep(i, 1, n) a[i] = read();
	if(!k) {
		rep(i, 1, n) if(a[i]) ++ans;
		rep(i, 1, n) b[i] = 0;
	}
	else if(k > n + 1) {
		rep(i, 1, n) b[i] = a[i];
	}
	else {
		rep(i, 1, n) b[i] = a[i];
		for(int l = 0, r = 1; r <= n; r++) {
			if(a[r] > k) continue;
			if(a[r] == k) {
				while(++l < r) if(a[l] < k) --cnt[a[l]];
				mex = 0;
			}
			else {
				++cnt[a[r]];
				while(cnt[mex]) ++mex;
				if(mex == k) {
					++ans;
					while(++l < r) if(a[l] < k) --cnt[a[l]];
					--cnt[a[r]];
					b[r] = k;
					mex = 0;
				}
			}
		}
	}
	write(ans, '\n');
	rep(i, 1, n) write(b[i], " \n"[i==n]);
	return 0;
}