猫耳少女小 R 与数列 Mex：最小修改次数

小 R 是一位可爱的猫耳少女，她喜欢研究数列的 mex。她有一个长度为 n 的数列 a，讨厌整数 k，因此她希望修改数列 a 的若干个元素为任意自然数，使得 a 的任意连续子串的 mex 都不等于 k。

请你求出最少需要修改多少个元素。

定义: 数列的 mex 被定义为数列中最小未出现的自然数，例如：

mex{1,2,3} = 0，因为 0 是自然数。
mex{0,1,3} = 2。
mex{0,1,2} = 3。

算法: 本题需要使用线段树和离散化。

代码: 由于代码较长，建议认真阅读。

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

const int N = 1e5 + 5;

int n, k;
int a[N], b[N];

struct node {
    int l, r;
    int mx, mn, tag;
} t[N << 2];

void pushup(int p) {
    t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx);
    t[p].mn = min(t[p << 1].mn, t[p << 1 | 1].mn);
}

void pushdown(int p) {
    if (t[p].tag) {
        t[p << 1].tag = t[p].tag;
        t[p << 1].mx = t[p].tag;
        t[p << 1].mn = t[p].tag;
        t[p << 1 | 1].tag = t[p].tag;
        t[p << 1 | 1].mx = t[p].tag;
        t[p << 1 | 1].mn = t[p].tag;
        t[p].tag = 0;
    }
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].mx = t[p].mn = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void modify(int p, int l, int r, int v) {
    if (l <= t[p].l && t[p].r <= r) {
        t[p].tag = v;
        t[p].mx = v;
        t[p].mn = v;
        return;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) modify(p << 1, l, r, v);
    if (r > mid) modify(p << 1 | 1, l, r, v);
    pushup(p);
}

int query(int p, int l, int r, int flag) {
    if (l <= t[p].l && t[p].r <= r) {
        if (flag) return t[p].mx;
        else return t[p].mn;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    int res = 0;
    if (l <= mid) res = max(res, query(p << 1, l, r, flag));
    if (r > mid) res = max(res, query(p << 1 | 1, l, r, flag));
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    build(1, 1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = i;
        while (l >= 1 && query(1, l, i, 0) != k) l--;
        while (r <= n && query(1, i, r, 1) != k) r++;
        if (query(1, l + 1, r - 1, 0) == k) {
            ans++;
            modify(1, l + 1, r - 1, k + 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}