P-9199-9202 「GMOI R2-T2」猫耳小 题解

link T1

小 R 有一个长度为 $n$ 的数列 $a$。她讨厌整数 $k$，因此她希望修改数列 $a$ 的若干个元素为任意自然数，使得 $a$ 的任意连续非空子串的 $\text{mex}$ 都不等于 $k$。

请你求出最少需要修改多少个元素，并给出方案。

$n\leq10^6$，值域为 $10^9$

---

显然的，有 $a_i=k$ 一定能满足。

因此先将 $a$ 按照 $k$ 进行分段。

考虑在一个段内从左到右扫描每个数，忽略所有 $>k$ 的数。如果当前已经扫描的数中包含了 $0\sim k-1$ 所有数，就把最后一个出现的数修改为 $k$。

在模拟赛的时候还想到了一种做法，即考虑直接架空一个 $<k$ 的数。

下面来证明这种方法一定更劣。

我们考虑架空的数一定是 $0\sim k-1$ 出现次数最小的数。

由于标准解法中每修改一次 $k$，就要使得每个数出现次数至少 $+1$，因此出现次数最小也会大于等于修改次数。

所以就不用管了。