DDOSvoid's Blog

CF 1129D Isolation

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/problemset/problem/1129/D

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个整数 $k$，要求将序列划分长若干段，且每段中恰好出现一次的数的个数不超过 $k$，求所有划分方法，对 $998244353$ 取模

$n\le 10^5$

Solution

令 $f[i]$ 表示划分成了多少段，每次新加入一个数，将会使 $[pre_i+1,i]$ 区间加 $1$，$[pre_{pre_i}+1, pre_i]$ 区间减一

容易转换题面为每次区间加一或减一，求权值小于等于 $k$ 的位置的 $f$​ 的和

考虑分块维护，每个块维护权值为 $s,s\in[1,n]$ 的 $f$​ 的和，由于每次修改只有加减 $1$，所以可以做到每次修改 $O(1)$ 维护全局答案

时间复杂度 $O(n\sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cmath>
#define maxn 100010
#define maxs 320
#define offset 100000
#define ll long long
using namespace std;

const int p = 998244353;

inline int inc(int x, int y) { return (x += y) >= p ? x - p : x; }

int n, k;

int num, blo, l[maxs], r[maxs], bl[maxn], add[maxs], d[maxs][maxn * 2], a[maxn], f[maxn];
void init_blo(int n) {
    blo = sqrt(n); num = (n + blo - 1) / blo;
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo; 
    } r[num] = n;
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
}

int ans;
void update(int L, int R, int v) {
    int Bl = bl[L], Br = bl[R];
    if (Bl == Br) {
        for (int i = L; i <= R; ++i) { 
            if (v == 1 && a[i] + add[Bl] == k) ans = inc(ans, p - f[i]); 
            if (v == -1 && a[i] + add[Bl] == k + 1) ans = inc(ans, f[i]);
            d[Bl][a[i] + offset] = inc(d[Bl][a[i] + offset], p - f[i]);
            a[i] += v;
            d[Bl][a[i] + offset] = inc(d[Bl][a[i] + offset], f[i]); 
        }
        return ;
    }
    for (int i = L; i <= r[Bl]; ++i) {
        if (v == 1 && a[i] + add[Bl] == k) ans = inc(ans, p - f[i]); 
        if (v == -1 && a[i] + add[Bl] == k + 1) ans = inc(ans, f[i]);
        d[Bl][a[i] + offset] = inc(d[Bl][a[i] + offset], p - f[i]);
        a[i] += v;
        d[Bl][a[i] + offset] = inc(d[Bl][a[i] + offset], f[i]);
    }
    for (int i = l[Br]; i <= R; ++i) {
        if (v == 1 && a[i] + add[Br] == k) ans = inc(ans, p - f[i]); 
        if (v == -1 && a[i] + add[Br] == k + 1) ans = inc(ans, f[i]);
        d[Br][a[i] + offset] = inc(d[Br][a[i] + offset], p - f[i]);
        a[i] += v;
        d[Br][a[i] + offset] = inc(d[Br][a[i] + offset], f[i]);
    }
    for (int i = Bl + 1; i < Br; ++i) {
        if (v == 1) ans = inc(ans, p - d[i][k - add[i] + offset]);
        if (v == -1) ans = inc(ans, d[i][k + 1 - add[i] + offset]); 
        add[i] += v;
    }
}

void update(int i, int v) {
    d[bl[i]][0 - add[bl[i]] + offset] = inc(d[bl[i]][0 - add[bl[i]] + offset], v);
}

int vis[maxn], pre[maxn];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k; init_blo(n); 
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        pre[i] = vis[x], vis[x] = i;
    }
    ans = f[1] = 1; update(1, f[1]);
    for (int i = 1; i <= n; ++i) {
        update(pre[i] + 1, i, 1);
        if (pre[i]) update(pre[pre[i]] + 1, pre[i], -1);
        f[i + 1] = ans; ans = inc(ans, f[i + 1]);
        if (i < n) update(i + 1, f[i + 1]); 
    } cout << f[n + 1] << "\n";
    return 0;
}