CF1129D Isolation

考虑 dp，令 \(f_i\) 为 \([1,i]\) 这个前缀的分段方案数。\(i\) 从小到大扫描线，动态维护 \(c_j\) 表示 \([j+1,i]\) 中只出现恰好一次的数的个数：

考虑如何维护 \(c_j\)，扫描线过程中维护 \(l_i\) 表示 \(a_i\) 上次出现的位置。那么 \(i-1\to i\) 相当于给 \([l_{l_i},l_i)\) 区间 \(-1\)，\([l_i,i)\) 区间 \(+1\)。

所以问题转化为：

• 单点修改 \(f_i\)。
• 区间修改 \(c_i\)。
• 区间（前缀）查询 \(c_i\le k\) 的 \(f_i\) 总和。

分块即可。复杂度 \(O(n\sqrt n)\)，可以做到线性空间但没必要。

不知道有没有 \(O(n\ \text{poly}(\log n))\) 做法。

// Problem: Isolation
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1129D
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

namespace vbzIO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define mt make_tuple
    #define mp make_pair
    #define fi first
    #define se second
    #define pc putchar
    #define pb emplace_back
    #define ins insert
    #define era erase
    typedef tuple<int, int, int> tu3;
    typedef pair<int, int> pi;
    inline int rd() {
        char ch = gh();
        int x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void wr(int x) {
        if (x < 0) x = ~(x - 1), putchar('-');
        if (x > 9) wr(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace vbzIO;

const int P = 998244353;
const int N = 1e5 + 100;
const int B = 330;

int n, k, a[N], f[N], lst[N], pre[N];
int b, lp[B], rp[B], pos[N], s[B], c[B][N], vl[N], t[B];

void clr(int id) {
	s[id] = 0;
	for (int i = lp[id]; i <= rp[id]; i++) c[id][vl[i]] = 0;
}

void reb(int id) {
	for (int i = lp[id]; i <= rp[id]; i++) 
		vl[i] += t[id], (c[id][vl[i]] += f[i]) %= P, (s[id] += (vl[i] <= k) ? f[i] : 0) %= P;
	t[id] = 0;
}

void add(int id) {
	if (k >= t[id]) (s[id] += P - c[id][k - t[id]]) %= P;
	t[id]++;
}

void del(int id) {
	t[id]--;
	if (k >= t[id]) (s[id] += c[id][k - t[id]]) %= P;
}

void upd(int l, int r, int op) {
	if (l > r) return;
	if (pos[l] == pos[r]) {
		clr(pos[l]); for (int i = l; i <= r; i++) vl[i] += op;
		return reb(pos[l]);
	}
	clr(pos[l]); for (int i = l; i <= rp[pos[l]]; i++) vl[i] += op; reb(pos[l]);
	clr(pos[r]); for (int i = lp[pos[r]]; i <= r; i++) vl[i] += op; reb(pos[r]);
	for (int i = pos[l] + 1; i <= pos[r] - 1; i++) 
		if (~op) add(i); else del(i);
}

int main() {
	n = rd(), k = rd(), b = sqrt(n);
    for (int i = 1; i <= n; i++) a[i] = rd();
    for (int i = 1; i <= b; i++)
    	lp[i] = (i - 1) * b + 1, rp[i] = i * b;
    if (rp[b] < n) b++, lp[b] = rp[b - 1] + 1, rp[b] = n;
    for (int i = 1; i <= b; i++)
    	for (int j = lp[i]; j <= rp[i]; j++)
    		pos[j] = i;
	for (int i = 1, ct = 0; i <= n; i++) {
		lst[i] = pre[a[i]], pre[a[i]] = i;
		if (!lst[lst[i]]) ct -= (lst[i] != 0); upd(max(1, lst[lst[i]]), lst[i] - 1, -1);
		if (!lst[i]) ct++; upd(max(1, lst[i]), i - 1, 1);
		for (int j = 1; j <= b; j++) (f[i] += s[j]) %= P;
		if (ct <= k) f[i] = (f[i] + 1) % P;
		clr(pos[i]), reb(pos[i]);
	}
	wr(f[n]);
    return 0;
}