最小修改次数：使数列子串的 mex 不等于 k

给定一个长度为 n 的数列 a，你需要修改若干个元素，使得 a 的任意连续子串的 mex 都不等于 k。求最少需要修改多少个元素。

本题中，数列的 mex 被定义为数列中最小未出现的自然数，例如：
mex{1,2,3}=0，因为 0 是自然数。
mex{0,1,3}=2。
mex{0,1,2}=3。

C++ 代码

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

const int N = 100010;
int a[N];
bool vis[N]; // 标记是否出现过
int mex[N]; // 存储 mex 值
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    memset(vis, 0, sizeof vis);
    memset(mex, 0, sizeof mex);

    int l = 1, r = 1, cnt = 0, res = 0;
    while (r <= n)
    {
        vis[a[r]] = true; // 标记出现过的数
        while (vis[cnt]) cnt ++ ; // 找到下一个未出现的数
        mex[r] = cnt; // 计算当前位置的 mex 值

        if (mex[r] == a[r]) // 如果 a[r] 等于 mex，需要修改
        {
            if (mex[l] == a[l]) vis[a[l]] = false; // 如果 l 位置也需要修改，需要将之前标记的数取消掉
            l ++ ; // 左指针右移
        }
        else res = max(res, r - l + 1); // 更新答案

        r ++ ; // 右指针右移
    }

    cout << res << endl;
    return 0;
}