水题，但是调了好久 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;
}