这道题目，是一道有点刺激的数据结构优化 $dp$ 题。

如何想到 $dp$:

我们看到，这道题是一个求方案数量的题目，那么只有递推（也就是简单 $dp$）和搜索这两种方式，而我不喜欢打搜索，就用 $dp$ 了。

如何设计 $dp$:

我们知道，题目中要求对序列进行分组，那么就是一道有关子序列的问题，我们就可以想到，一段子序列是两个子序列的差集，即$[l,r]$ 是 $[1,r]$ 和 $[1,l]$ 的差集，所以可以设计关于前缀的 $dp$ （这段话适用于大多数子序列的题目）

所以，设 $f[i]$表示将$a_{1 \dots i}$ 分组的方案数。

那么，我们只要找到一个$[1,i]$的后缀$[k+1,i]$，满足其中所有数之和不小于0，那么在合法的分组方案中，一定有这一段被作为最后一组的情况。

那一共有多少这种方案呢？

在这种方案下，我们要让$[1,k]$ 也符合要求，因为在这里后缀是固定的，所以情况数就是让$[1,k]$符合要求的方案数。

就是$f[k]$

所以，我们的状态转移方程就写出来了。

$$f[i]=\sum\limits_{a_{k+1}+a_{k+2}+\dots+a_i\ge 0,k \le i}f[k]$$

（其实上面啰嗦一大堆，是为了让各位看官获得一个普适化的思维方式）

简化一下状态转移方程，令 $sum[i]=\sum\limits_{j=1}^i a[j]$，则状态转移方程可以写成：

$$f[0]=1,f[i]=\sum\limits_{sum[i] \ge sum[k],k \le i}f[k]$$

暴力枚举 $i,k$ 的话，时间复杂度为 $\Theta(n^2)$

然而，要是 $n$ 再小点就好了.......

$n \le 2\times 10^5$

看到这个范围，你才知道这为什么是蓝题。

---

如何优化时间：

我们可以新建一个序列$q$ 其中$q[sum[i]]=f[i],i\in[0,n]$

我们维护一个下标$i$,从左到右扫描。（这样就天然满足了方程中$k \le i$这一条件）

那么对于$f[i]$而言，我们只要求$\sum\limits_{j=\min\{sum[k]\}}^{sum[i]}q[j]$,求完之后再让$q[sum[i]]\leftarrow f[i]$.(其中$\min\{sum[k]\}$是指所有$sum$中的最小值）

那么，这就是个单点修改，询问前缀和的题目，可以用树状数组求解.

但是，我们发现，$-10^9\le sum[i]\le 10^9,i \in[1,n]$，是完全没法用普通数组做的。

我们可以用一个数的排名代替这个数（排名定义为比它小的个数加1）

我们知道，这样子的话，在某个数前面的数还是在某个数前面，结果不会有改变。

其实这个过程就是离散化（将无限空间里的有限个体映射到有限空间中）

这种代替方式最为常用，也好写。

但是，我们映射的时候要加上0号结点，因为有一点:$f[0]=1$

如何求一个数的排名？

排序之后看它的下标，可以用二分查找，这里不再赘述。

---

代码：

各位看官，随我来！

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],sum[N],vals[N],n,b[N],mod=1e9+9;
/*
	a为原序列
    sum 为前缀和
    vals为一个附加空间，用来存排序之后的sum
    b 为离散化后的序列
*/
int f[N];
#define lowbit(x) (x&(-x))
int tr[N];
//
inline void update(int pos,int num)   //树状数组单点修改
{
	int x=pos;
	while(x<=n)
	{
		tr[x]+=num;
		tr[x]%=mod;
		x+=lowbit(x);
	}
}
inline int _sum(int pos)   //树状数组求前缀和
{
	int res=0,x=pos;
	while(x)
	{
		(res+=tr[x])%=mod;
		x-=lowbit(x);
	}
	return res;
}
int tot=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
//------------------读入，预处理--------------------
	for(int i=0;i<=n;i++)  //记得加上0
	vals[++tot]=sum[i];     
	sort(vals+1,vals+tot+1);  //排序
	tot=unique(vals+1,vals+tot+1)-vals-1;  //去重，否则相同的数排名不同
	for(int i=0;i<=n;i++)
	b[i]=lower_bound(vals+1,vals+tot+1,sum[i])-vals;  //二分查找
//------------------离散化----------------------------
	update(b[0],f[0]=1);   //加入0号结点
	for(int i=1;i<=n;i++)
	{
		f[i]=_sum(b[i]);   //求出 q 序列中的前缀和
		update(b[i],f[i]);   //令q[b[i]]=f[i]
	}
	cout<<f[n]<<endl;   //输出答案
    return 2147483647;
}

有问题请评论，不喜勿喷。

by hansang:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
const LL P=1e9+9;
int n; LL c[N], a[N], b[N];
void add(LL x, LL w){
    for(int i=x; i<=n; i+=i&-i) c[i]=(c[i]+w)%P;
}
LL query(LL x){
    LL res=0;
    for(int i=x; i>=1; i-=i&-i) res=(res+c[i])%P;
    return res;
}
int main(){
    //freopen("a.in", "r", stdin);
    scanf("%d", &n); a[0]=b[0]=0;
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        a[i]+=a[i-1];
        b[i]=a[i];
    }
    sort(b, b+n+1);
    int len=unique(b+1, b+n+1)-b-1;
    for(int i=0; i<=n; i++){
        a[i]=lower_bound(b, b+len+1, a[i])-b+1;
    }
    add(a[0], 1); LL ans=0;
    for(int i=1; i<=n; i++){
        ans=query(a[i]);
        add(a[i], ans);
    }
    printf("%lld\n", ans%P);
    return 0;
}

超时：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , P = 1e9+9;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
ll  s[N] , f[N];
int main() {
    int n;qr(n);
    s[0] = 0;
    for(int i = 1 , x; i <= n; i++) qr(x) , s[i] = s[i - 1] + x;
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        if(s[i] >= 0) 
            for (int j=0; j < i; j++) 
                if(s[j] >= 0 && s[i] - s[j] >= 0) 
                    (f[i] += f[j])%=P;
    printf("%lld\n",f[n]);
    return 0;
}

标程：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , P = 1e9 + 9;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
int  n ;
ll a[N] , b[N] , s[N] , f[N] , c[N];
inline void add(int x , ll k)
{
    for( ; x <= n; x += x & -x) c[x] += k;
}
inline ll sum(int x)
{
    ll ans = 0;
    for( ; x; x -= x & -x) ans += c[x];
    return ans;
}
int main() {
    qr(n);
    s[0] = 0;for(int i = 1 , x; i <= n; i++) qr(x) , b[i]=s[i] = s[i - 1] + x;
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+n+1)-b-1;
    for(int i = 1; i <= n; i++)  a[i] = lower_bound(b+1,b+cnt+1,s[i]) - b;
    for(int i = 1; i <= n; i++)
        if(s[i] >= 0) 
            f[i]=(sum(a[i]) + 1)%P,
            add(a[i],f[i]);
    printf("%lld\n",f[n]);
    return 0;
}