[CF 1129 D] Isolation

Posted on | Edited on | In , | Views:

题目链接

CF 1129 D

题目大意

现在有一个数列，长度为$n$，其中每个数均$\le n$，要求把数列分成若干段，使得这个数列每段中只出现$1$次的数均不超过$k$个。
$k \le n \le 10^5$

做法

首先$n^2$的$dp$非常显然。

我们考虑构造一个序列$v$，$\sum\limits_{i=l}^{r}v_i$表示区间$[l,r]$中仅出现一次的数的个数。
考虑如何构造$v$
我们每次新加进来一个数，$v_i=1$，$v_{pre[i]}=-1$，$v_{pre[pre[i]]}=0$，$pre[i]$是所有位置上的数与我相同的位置中最靠近我的一个，当然，是在我前面。
我们在对$v$做一次前缀和，得到数组$S$，那么我们上面的式子可以改写为

把问题转化一下。
维护一个数列，支持区间加，以及区间查询$S$小于一个数的$f$的和。
我们对原序列分块，每个块内维护权值的后缀和，我们对于每个区间用一个$lazy$标记维护整个块都加的值。如果有一个块有一部分被修改了，我们就暴力重构整一个块，所以每次修改的复杂度是$O(块大小)+O(块数)$，可以做到$\sqrt n$。
询问的时候，如果是整块，那么就先处理一下$lazy$标记，再在后缀和上查询一下就好了。
非整块部分暴力即可。
这题还有一些比较好的性质，我们每次插入一个数都只会改变最多两个区间的$S$值。
此外，在块内维护后缀和的时候还有一些小$tips$，发现$abs(S_i-S_{i-1})\le 1$的，所以我们把一个块内所有的$S$值，都减去最小的$S$值，那么$S$的区间是不会超过块大小的。最后在在整个区间的$lazy$标记上把减去的那个数加回来就好了。

代码

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,k,unit,tot;
int be[N],st[N],en[N],a[N],sum[2055][2055],f[N],pre[N],now[N],lazy[N],S[N];
const int P=998244353; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
void reset(int u){
    for (int i=st[u];i<=en[u];i++) S[i]+=lazy[u]; 
    lazy[u]=0;
    int minn=S[st[u]];
    for (int i=st[u];i<=en[u];i++) minn=min(minn,S[i]);
    for (int i=st[u];i<=en[u];i++) S[i]-=minn;
    memset(sum[u],0,sizeof(sum[u]));
    for (int i=st[u];i<=en[u];i++) sum[u][S[i]]=Inc(sum[u][S[i]],f[i]);
    for (int i=unit-1;i>=0;i--) sum[u][i]=Inc(sum[u][i],sum[u][i+1]);
    lazy[u]=minn;
}
void change(int L,int R,int data){
    if (be[L]==be[R]){
        for (int i=L;i<=R;i++) S[i]+=data;
        reset(be[L]);
    }
    else{
        for (int i=be[L]+1;i<=be[R]-1;i++) lazy[i]+=data;
        for (int i=L;i<=en[be[L]];i++) S[i]+=data;
        reset(be[L]);
        for (int i=st[be[R]];i<=R;i++) S[i]+=data;
        reset(be[R]);
    }
}
int query(int R,int lim){
    //printf("query %d %d\n",R,lim);
    if (R==0) return 0;
    int ret=0;
    for (int i=1;i<be[R];i++){
        if (lim-lazy[i]>unit) continue;
        ret=Inc(ret,sum[i][max(lim-lazy[i],0)]);
    }
    for (int i=st[be[R]];i<=R;i++){
        if (S[i]+lazy[be[i]]>=lim) ret=Inc(ret,f[i]);
    }
    //for (int i=1;i<=R;i++){
    //    if (S[i]+lazy[be[i]]>=lim) ret=Inc(ret,f[i]);
    //}
    return ret;
}
int main(){
    read(n),read(k);
    unit=sqrt(n);
    for (int i=1;i<=n;i++){
        read(a[i]);
        pre[i]=now[a[i]];
        now[a[i]]=i;
    } 
    for (int i=1;i<=n;i++){
        be[i]=(i-1)/unit+1;
        if (be[i]!=be[i-1]){
            en[be[i-1]]=i-1;
            st[be[i]]=i;
        }
    }
    tot=be[n];
    en[tot]=n;
    f[0]=1;
    S[0]=0;
    for (int i=1;i<=n;i++){
        if (be[i-1]!=be[i]) S[i]=S[i-1]+1+lazy[be[i-1]];
        else S[i]=S[i-1]+1; 
        if (pre[pre[i]]) change(pre[pre[i]],i,1);
        if (pre[i]) change(pre[i],i,-2);
        f[i]=query(i-1,S[i]+lazy[be[i]]-k);
        if (S[i]+lazy[be[i]]<=k) f[i]++;
        if (i==en[be[i]]) reset(be[i]);
    }
    printf("%d",f[n]);
    return 0;
}