CF1129D Isolation

(Updated: )
oi
,

题目链接：CF1129D

给定一个长度为 $n$ 的序列 $a_{1\sim n}$，把它分割成若干段，使得每段出现过恰好一次的元素个数 $\leq k$，求方案数对 $998244353$ 取模的结果。

$1\leq k\leq n \leq 10^5,1\leq a_i\leq n$。

Solution

1 朴素 DP

不妨设 $f_i$ 表示前 $i$ 个数的答案，设 $s_j$ 为 $a[j+1\dots i]$ 出现过恰好一次的元素个数，显然有：
$$
f_i=\sum_{s_j\leq k} f_j
$$
时间复杂度 $O(n^2)$，显然不能接受。

2 分块优化

考虑按顺序加入每个数字，会使 $\forall j\in[p_{p_i},p_i-1]$ 所有 $s_j$ 减 $1$，$\forall j \in [p_i,i-1]$ 所有 $s_j$ 加 $1$。

那么我们现在的问题就转化为两类操作：

  1. 区间 $\pm 1$
  2. 求所有权值 $\leq k$ 的 $f$ 值之和。
  3. 单点修改 $f$ 值。

显然这个东西不太可能做到 $\text{polylog}$，那么考虑分块。

只需要每个块开个桶记录一下每个 $s$ 的 $f$ 之和，操作 $1$ 只需要打个 $tag$ 然后维护一下答案即可。

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

Code

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
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,M=sqrt(N)+10,X=998244353;
int n,S,K,p[N],v[N],bl[N],L[N],R[N],tot,s[N],tg[M],f[N],g[M][N<<1],Ans;
I void cL(CI k){RI i;for(i=L[k];i<=R[k];i++) g[k][s[i]+N]=0,s[i]+tg[k]<=K&&(Ans-=f[i],Ans%=X);}
I void rB(CI k){RI i;for(i=L[k];i<=R[k];i++) (g[k][s[i]+N]+=f[i])%=X,s[i]+tg[k]<=K&&(Ans+=f[i],Ans%=X);}
I void UF(CI l,CI r,CI v){RI i;cL(bl[l]);for(i=l;i<=r;i++) s[i]+=v;rB(bl[l]);}
I void UB(CI l,CI r,CI v){RI i;for(i=l;i<=r;i++) v<0?Ans+=g[i][K+1-tg[i]+N]:Ans-=g[i][K-tg[i]+N],Ans%=X,tg[i]+=v;}
I void U(CI l,CI r,CI v){RI bL=bl[l],bR=bl[r];if(bL==bR) return UF(l,r,v);return bL+1<=bR-1&&(UB(bL+1,bR-1,v),0),UF(l,R[bL],v),UF(L[bR],r,v);}
I void A(CI p,CI v){if(f[p]=Ans,Ans+=f[p],Ans%=X,R[bl[p]]==p) cL(bl[p]),rB(bl[p]);}
int main(){
    RI i,x;for(read(n,K),S=sqrt(n),i=1;i<=n;i++) bl[i]=(i-1)/S+1,!((i-1)%S)&&(R[tot]=i-1,L[++tot]=i);R[tot]=n;
    for(f[0]=Ans=1,i=1;i<=n;i++) read(x),p[i]=v[x],p[i]<=i-1&&(U(p[i],i-1,1),p[p[i]]<=p[i]-1&&(U(p[p[i]],p[i]-1,-1),0)),v[x]=i,A(i,Ans);
    return writeln((f[n]+X)%X),0;
}