CF1129D Isolation
题目链接：CF1129D
给定一个长度为 n 的序列 a_{1sim n}，把它分割成若干段，使得每段出现过恰好一次的元素个数 leq k，求方案数对 998244353 取模的结果。
1leq kleq n leq 10^5,1leq a_ileq n。
Solution
1 朴素 DP
出现过恰好一次的元素个数，显然有：
时间复杂度
2 分块优化
考虑按顺序加入每个数字，会使 forall jin[p_{p_i},p_i-1] 所有 s_j 减 1，forall j in [p_i,i-1] 所有 s_j 加 1。
那么我们现在的问题就转化为两类操作：
- 区间 pm 1
- 求所有权值 leq k 的 f 值之和。
- 单点修改 f 值。
显然这个东西不太可能做到 text{polylog}，那么考虑分块。
只需要每个块开个桶记录一下每个 s 的 f 之和，操作 1 只需要打个 tag 然后维护一下答案即可。
时间复杂度 O(nsqrt n)。
Code
代码语言：javascript复制#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 '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;
}
