设 \(f_i\) 表示最后一个区间以 \(a_i\) 结尾的方案总数，也即前 \(i\) 个数的方案总数。最后的答案是 \(f_n\)。
很容易得到转移方程：
\[f_i = \sum_{j=1}^{i-1}f_j \]其中，需要保证 \(a_i \sim a_j\) 是一个合法区间才能累加，这个检查的过程可以通过 \(j\) 倒序并计算不合法的数的个数，为 \(0\) 时代表是合法区间。
时间复杂度 \(O(N^2)\)，附一份代码：
#include<cstdio>
using namespace std;
const int N=2e5+5,M=15,P=998244353;
int n,a[N],m,s[M];
bool no[N];
long long f[N];
int cnt[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
scanf("%d",&s[i]);
no[s[i]]=true;
}
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=n;j++)
cnt[j]=0;
int ins=0;
for(int j=i;j>=1;j--) //range[j,i]
{
if(no[cnt[a[j]]]) ins--;
cnt[a[j]]++;
if(no[cnt[a[j]]]) ins++;
if(!ins) f[i]=(f[i]+f[j-1])%P;
}
}
printf("%lld\n",f[n]);
return 0;
}
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e5+5,M=15,P=998244353;
int n,a[N],m,s[M];
long long f[N]; //f[i]表示前i个数分段的方案数
namespace SegmentTree{
struct SegmentTree{
int l,r;
int dat;
int add,mintag;
/*
* mintag记录区间最小标记
* dat记录带有区间最小标记的f值之和
* add作为延迟标记更新mintag
*/
}tree[N<<2];
void update(int p)
{
tree[p].add=0;
tree[p].mintag=min(tree[p<<1].mintag,tree[p<<1|1].mintag);
//区间的最小标记为两子区间最小标记的最小值
if(tree[p<<1].mintag==tree[p<<1|1].mintag)
tree[p].dat=(tree[p<<1].dat+tree[p<<1|1].dat)%P;
//如果两子区间的最小标记相同，就可以合并两个区间的最小标记元素之和
else
{
if(tree[p<<1].mintag<tree[p<<1|1].mintag) tree[p].dat=tree[p<<1].dat;
else tree[p].dat=tree[p<<1|1].dat;
/*
* 不同的话去最小标记更小的子区间的最小标记元素之和
* 因为上面总区间的最小标记就是由这个最小标记更小的子区间更新而来
* 所以这里的最小标记元素和也需要跟随这个子区间
*/
}
return;
}
void spread(int p) //下传延迟标记
{
if(tree[p].add)
{
tree[p<<1].add+=tree[p].add;
tree[p<<1|1].add+=tree[p].add;
tree[p<<1].mintag+=tree[p].add;
tree[p<<1|1].mintag+=tree[p].add;
tree[p].add=0;
}
return;
}
void Build(int l,int r,int p=1)
{
tree[p].l=l,tree[p].r=r;
if(l==r) return;
int mid=l+r>>1;
Build(l,mid,p<<1),Build(mid+1,r,p<<1|1);
return;
}
void add_range(int l,int r,int k,int p=1) //区间修改，为所有区间增加一个标记
{
if(l<=tree[p].l&&tree[p].r<=r)
{
tree[p].add+=k;
tree[p].mintag+=k; //区间最小标记一定会被同时增加
return;
}
spread(p);
int mid=tree[p].l+tree[p].r>>1;
if(l<=mid) add_range(l,r,k,p<<1);
if(r>mid) add_range(l,r,k,p<<1|1);
update(p);
return;
}
void add_point(int x,int k,int p=1) //单点修改，这里用作将一个f值打入线段树中（f[x]=k）
{
if(tree[p].l==tree[p].r)
{
tree[p].dat=k; //修改此处对应的f值
return;
}
spread(p);
int mid=tree[p].l+tree[p].r>>1;
if(x<=mid) add_point(x,k,p<<1);
else add_point(x,k,p<<1|1);
update(p);
return;
}
} //namespace SegmentTree
using namespace SegmentTree;
vector<int> pos[N]; //pos[i][j]表示i第j次出现的位置
int cnt[N]; //cnt[i]表示i已经出现的次数
int main()
{
scanf("%d%d",&n,&m);
Build(0,n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&s[i]);
f[0]=1,add_point(0,1);
for(int i=1;i<=n;i++)
pos[i].push_back(0);
for(int i=1;i<=n;i++)
{
pos[a[i]].push_back(i);
cnt[a[i]]++;
for(int j=1;j<=m;j++) //对于第j个不合法次数来说
{
if(cnt[a[i]]>=s[j]) //不合法标记
{
/*
* 以i结尾关于x和s[j]不合法的区间左端点
* 是从“x第(cnt[x]-s[j])次出现的位置”
* 到“x第(cnt[x]-s[j]+1)次出现的位置”
*/
int l=pos[a[i]][cnt[a[i]]-s[j]]; //进入不合法区间的位置
int r=pos[a[i]][cnt[a[i]]-s[j]+1]; //退出不合法区间的位置
add_range(l,r-1,1); //为区间打上不合法标记
}
if(cnt[a[i]]>s[j]) //撤销先前的标记
{
int l=pos[a[i]][cnt[a[i]]-s[j]-1];
int r=pos[a[i]][cnt[a[i]]-s[j]];
/*
* cnt相比上一次都多减了一个1
* 相当于获得上一次出现时的l和r
*/
add_range(l,r-1,-1); //-1抵消以抵消上次标记
}
}
if(tree[1].mintag==0)
{
f[i]=tree[1].dat;
/*
* 此时标记为0的，即对于所有s[j]都合法的元素
* 就可以累加到f[i]当中，与f[i]组合成合法的区间
*
* 所以在此处添加一个if语句判断mintag是否为0
* 其实更合理一些，同样可过
* 至于不加为什么能过……世界未解之谜
*/
add_point(i,f[i]); //将新的f值打入到线段树中
}
}
printf("%lld\n",f[n]);
return 0;
}