我一开始想的是O（n2）的做法，就是暴力dp。
考虑对于一个位置 i ，如果说存在（1 <= j < i ），使得sum[ i ] >= sum [ j ] ，那么 j 到 i 就可以分为一组，i 的方案数就加上 j 的方案数。这是O（n2）的，对于100000这样的数据显然过不了。
考虑优化：
我在想这个问题的时候，感觉，要用 logn 的时间求出存在（1 <= j < i ），使得sum[ i ] >= sum [ j ]的dp[ j ] 的和常规想法几乎是不可能的……所以肯定要维护一个数据结构。
我一开始想的是平衡树，旋转到根后，维护儿子的和（dp和），这样在找到sum [ j ] 的时候，加上左儿子的和就可以了，但是我并不想写平衡树……
然后我就想，如果说sum值是有序的，那么 “ 如果说存在（1 <= j < i ），使得sum[ i ] > sum [ j ] ” 这个问题就可以用线段树维护了。就会发现这个求sum顺序对的问题，就是二位偏序而已。那么思路就有了：sum排序离散化，对于现在的 i ，在线段树sum [ i ] 位置上加上【1，sum [ i ] 】的和。这样既满足 i 有序，也满足加上了所有sum[ i ] > = sum [ j ]的 dp [ j ] 的值。
温馨概括：线段树上第 i 位代表排名为第 i 小的 sum 的 dp 值。
我在写的时候犯了几个错误……
第一个，就是写线段树求和的时候，比如应该在左区间找对应区间，我到左区间后把对应区间减半了……
第二个，也比较重要。最后的答案是第 n 次求和的值，而不是最后求sum [ n ] 位置的和。我想了半天……才意识到自己太傻了，首先dp [ n ] 的值本来就是第 n 次求和的那个值；再说，我在对应位置加上这个值之前，这个位置很有可能都有值了啊，再求不就多了嘛！说得严谨点：每一个dp [ i ] 只被ans记录一遍，我们再后来并不能求出任何一个单独的dp [ i ] 。
所以上面的概括严禁点就是：
线段树上第 i 位代表排名为第 i 小的 多个sum 的 dp 值之和。
我感觉这道题挺不错的（好想我感觉每道题都挺不错……）
代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<cstdlib> using namespace std; #define maxn 5000005 #define ls now<<1 #define rs now<<1|1 #define int long long #define mod 1000000009 int sum[maxn],l[maxn],r[maxn]; int dp[maxn],f[maxn],a[maxn],p[maxn],pre[maxn]; int n,T; int find(int x) { int ans=0,L=1,R=T; while(L<=R) { int mid=(L+R)>>1; if(p[mid]>=x) { ans=mid; R=mid-1; } else L=mid+1; } return ans; } void up(int now) { f[now]=(f[ls]+f[rs])%mod; } void build(int now,int L,int R) { l[now]=L; r[now]=R; if(L==R) return ; int mid=(L+R)>>1; build(ls,L,mid); build(rs,mid+1,R); } int query(int now,int L,int R) { if(l[now]==L&&r[now]==R) return f[now]; int mid=(l[now]+r[now])>>1; if(R<=mid) return query(ls,L,R); else if(L>mid) return query(rs,L,R); else return (query(ls,L,mid)+query(rs,mid+1,R))%mod; } void update(int now,int id,int x) { if(l[now]==r[now]&&l[now]==id) { (f[now]+=x)%=mod; return ; } int mid=(l[now]+r[now])>>1; if(id<=mid) update(ls,id,x); else update(rs,id,x); up(now); } main() { scanf("%lld",&n); for(int i=1; i<=n; i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; pre[i]=sum[i]; } sort(sum+1,sum+n+1); T=unique(sum+1,sum+n+1)-sum-1; for(int i=1; i<=T; i++) p[i]=sum[i]; build(1,1,T); int ans; for(int i=1; i<=n; i++) { ans=query(1,1,find(pre[i]))%mod;// 1是dp[0] if(pre[i]>=0) ans++; update(1,find(pre[i]),ans); } printf("%lld ",ans); return 0; }