奶牛抗议

描述

约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字
可正可负。约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之
和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必
须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。约翰想知道有多少种分组的方案，由于
答案可能很大，只要输出答案除以1000000009 的余数即可。

输入

第一行：单个整数N，1 ≤ N ≤ 100000
第二行到第N + 1 行：第i + 1 行有一个整数Ai，10^5 ≤ Ai ≤ 10^5

输出

单个整数：表示分组方案数模1000000009 的余数

样例

输入

输出

提示

说明
解释:如果分两组，可以把前三头分在一组，或把后三头分在一组；
如果分三组，可以把中间两头分在一组，第一和最后一头奶牛自成一组；最后一种分法是把四头奶牛分在同一组里。

思路：

在做这道题之前，我们不妨先来想想这道题暴力怎么做。于是我们很容易得到一个简单的暴力转移方程：

令f[i]表示到i的方案数，有f[i]=∑f[j],k=j+1∑i a[k]≥0
写成前缀和的形式便是f[i]=∑f[j],sum[i]-sum[j]≥0，于是

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define mod 1000000009 
 4 using namespace std;
 5 ll n,sum[100005],ans,f[100005],a[100005];
 6 int main()
 7 {
 8     scanf("%lld",&n);
 9     for(ll i=1;i<=n;i++)
10     {
11         scanf("%lld",&a[i]);
12         sum[i]=sum[i-1]+a[i];
13     }
14     f[0]=1;
15     for(ll i=1;i<=n;i++)
16         for(ll j=0;j<i;j++)
17             if(sum[i]-sum[j]>=0)
18                 f[i]=(f[i]+f[j])%mod;
19     printf("%lld
",f[n]);
20     return 0;
21 }

可是这是n^2，怎么优化？

我们再来仔细看看这个代码，注意到这一句话：sum[i]-sum[j]>=0，我们将其转化一下是不是可以变成sum[i]>=sum[j]呢？

这时候我们发现相当于求在i前面并且前缀和小于sum[i]的所有f[i]和，这就可以用一个树状数组优化了，在树状数组维护下标为sum[i]，f[i]的前缀和。对于每个f[i]即为树状数组

上sum[i]的前缀和。

这里需要注意的是前缀和可能为负，而树状数组下标不能为负，所以我们要离散化一下。于是，上代码：

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define mod 1000000009
 4 #define lowbit(x) x&(-x)
 5 using namespace std;
 6 ll sum[1000001],n,f[1000001],b[1000001],num,a[1000001];
 7 struct data {
 8     ll v,id;
 9 } t[1000001];
10 bool cmp(data x,data y) {
11     if(x.v==y.v)
12         return x.id<y.id;
13     else
14         return x.v<y.v;
15 }
16 void add(ll x,ll val) {
17     while(x<=n+1) {
18         sum[x]+=val;
19         x+=lowbit(x);
20     }
21 }
22 ll ask(ll x) {
23     ll ans=0;
24     while(x) {
25         ans+=sum[x];
26         x-=lowbit(x);
27     }
28     return ans;
29 }
30 int main() {
31     scanf("%lld",&n);
32     for(ll i=1; i<=n; i++) {
33         scanf("%lld",&a[i]);
34         f[i+1]=f[i]+a[i];
35     }
36     f[1]=0;
37     for(ll i=1; i<=n+1; i++) {
38         t[i].v=f[i];
39         t[i].id=i;
40     }
41     sort(t+1,t+n+2,cmp);
42     for(ll i=1; i<=n+1; i++)
43         b[t[i].id]=i;//离散化
44     add(b[1],1);
45     for(ll i=2; i<=n+1; i++) {
46         num=ask(b[i])%mod;
47         add(b[i],num);
48     }
49     printf("%lld
",num%mod);
50     return 0;
51 }

值得注意的是，我在这里把前0个数前缀和为零的情况也插入到了树状数组，所以注意一下小细节。

如果有什么不对的地方欢迎各位巨佬指正。

撒花~~~