「解题报告」CF1129D Isolation

水题，但是调了好久 qwq

显然是 DP，出现次数显然分块，那就数据结构优化 DP 呗。

我们可以维护出当前点到每个点这段区间内有多少个出现次数为 \(1\) 的数，这个右端点每拓展一位修改的左端点一定是连续的区间。分块维护这个东西，如果是散块暴力重构暴力加，如果是整块那给整块打个加标记。

发现，加标记的差值是 \(\pm 1\)，那么我们可以对每一块动态维护 \(\le k - \Delta\) 的和，可以 \(O(1)\) 维护。然后剩下的就随便维护了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, B = 320, MAXB = 355, P = 998244353;
int n, k;
int a[MAXN];
int bl[MAXN], L[MAXB], R[MAXB];
int lst[MAXN], llst[MAXN];
int f[MAXN];
int c[MAXN];
struct Block {
    int a[MAXN], delta, sum;
    void add(int d, int v) {
        a[d] = (a[d] + v) % P;
        if (d <= k - delta) sum = (sum + v) % P;
    }
    void addDelta(int v) {
        if (v == 1) {
            if (k - delta >= 0 && k - delta <= n)
                sum = (sum - a[k - delta] + P) % P;
            delta++;
        } else if (v == -1) {
            delta--;
            if (k - delta >= 0 && k - delta <= n)
                sum = (sum + a[k - delta]) % P;
        }
    }
} b[MAXB];
void rebuild(int i) {
    int newsum = 0;
    for (int j = L[i]; j <= R[i]; j++) {
        b[i].add(c[j], P - f[j]);
        c[j] += b[i].delta;
        b[i].add(c[j], f[j]);
        if (c[j] <= k) newsum = (newsum + f[j]) % P;
    }
    b[i].delta = 0;
    b[i].sum = newsum;
}
void add(int l, int r, int v) {
    if (bl[l] == bl[r]) {
        rebuild(bl[l]);
        for (int i = l; i <= r; i++) {
            b[bl[l]].add(c[i], P - f[i]);
            c[i] += v;
            b[bl[l]].add(c[i], f[i]);
        }
    } else {
        rebuild(bl[l]);
        for (int i = l; i <= R[bl[l]]; i++) {
            b[bl[l]].add(c[i], P - f[i]);
            c[i] += v;
            b[bl[l]].add(c[i], f[i]);
        }
        rebuild(bl[r]);
        for (int i = L[bl[r]]; i <= r; i++) {
            b[bl[r]].add(c[i], P - f[i]);
            c[i] += v;
            b[bl[r]].add(c[i], f[i]);
        }
        for (int i = bl[l] + 1; i <= bl[r] - 1; i++) {
            b[i].addDelta(v);
        }
    }
}
void insert(int d) {
    rebuild(bl[d]);
    b[bl[d]].add(c[d], f[d]);
}
int query() {
    int ret = 0;
    for (int i = 1; i <= bl[n]; i++) {
        ret = (ret + b[i].sum) % P;
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int l = 1, r, i = 1; l <= n; l = r + 1, i++) {
        r = min(n, r + B - 1);
        L[i] = l, R[i] = r;
        for (int j = l; j <= r; j++) {
            bl[j] = i;
        }
    }
    f[1] = 1;
    insert(1);
    for (int i = 1; i <= n; i++) {
        if (lst[a[i]]) {
            add(llst[a[i]] + 1, lst[a[i]], -1);
        }
        add(lst[a[i]] + 1, i, 1);
        llst[a[i]] = lst[a[i]], lst[a[i]] = i;
        f[i + 1] = query();
        if (i != n) insert(i + 1);
    }
    printf("%d\n", f[n + 1]);
    return 0;
}