思路

考虑设 $c_l$ 表示 $\sum_{r=l}^nf((a_l,a_{l+1},\dots,a_r))$。然后考虑枚举左端点，并对每个 $l$ 找出一个最大的 $r$，满足 $\sum_{i=l}^ra_i\le s$，那么显然，当右端点在 $l$ 到 $r$ 内时，答案是 $1$，共有 $r-l+1$ 种情况。如果不在呢？显然，可以拆成 $[l,r]$ 和 $[r+1,n]$ 两段区间考虑，即对于这样的右端点 $p$，答案为 $f((a_l,a_{l+1},\dots,a_r))+f((f_{r+1},f_{r+2},\dots,f_p))$。前一项是 $1$，而后一项之和就等于 $c_{r+1}$。所以可得 $c_l=r-l+1+c_{r+1}+n-r$。倒着推即可，最终答案为所有 $c_i$ 之和。找 $r$ 用二分即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,c,a[N],sum[N],f[N],ans;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
signed main(){
	n=read();c=read();
	for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];
	f[n]=1;
	for(int i=n-1;i>=1;i--){
		int r=lower_bound(sum+1,sum+1+n,sum[i-1]+c+1)-sum-1;
		f[i]=r-i+1+f[r+1]+n-r;
	}
	for(int i=1;i<=n;i++)ans+=f[i];
	cout<<ans;
	return 0;
}