题目：[USACO11FEB]Generic Cow Protests

---

这道题首先想到DP。

考虑：阶段数一般为序列编号，如果我们设第二维状态用以表示划分段数，空间复杂度不够。综上，我们使用\(dp[i]\)直接表示第i位所有情况和。

有方程：

\[dp[i]=\sum_{j=1}^{i-1}{dp[j]}(sum[i]-sum[j]≥0) \]

时间复杂度为\(O(n^2)\)。

实际上，我们使用数据结构优化时间复杂度。考虑条件：

\[sum[i]-sum[j]≥0 \]

移项得：

\[sum[i]≥sum[j] \]

也就是说，它的状态值是所有小于\(sum[i]\)的位置，因而可以使用树状数组或线段树。

具体地，我们可以将所有前缀和进行离散化，按照值域建立一颗线段树，从\(1\)到\(n\)一次统计答案。
时间复杂度为\(O(nlogn)\)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int SIZE = 100000 + 10, mod = 1e9 + 9;
int n, tot = 0, a[SIZE], b[SIZE], table[SIZE], s[SIZE], c[SIZE], dp[SIZE] = {};
int lowbit(int x)
{
	return x & (-x);
}
void discrete()
{
	sort(b, b + n + 1);
	table[++ tot] = b[0];
	for(int i = 1; i <= n; ++ i) if(b[i] != b[i - 1]) table[++ tot] = b[i];
	return;
}
int query(int v)
{
	int L = 1, R = tot, mid;
	while(L < R)
	{
		mid = L + R >> 1;
		if(table[mid] < v) L = mid + 1;
		else R = mid; 
	}
	return L;
}
void add(int x, int v)
{
	while(x <= n)
	{
		c[x] = (c[x] + v) % mod;
		x += lowbit(x);
	}
	return;
}
int ask(int x)
{
	int res = 0;
	while(x)
	{
		res = (res + c[x]) % mod;
		x -= lowbit(x);
	}
	return res;
}
int main()
{
	scanf("%d", &n);
	memset(a, 0, sizeof(a));
	memset(s, 0, sizeof(s));
	for(int i = 1; i <= n; ++ i) 
	{
		scanf("%d", &a[i]);
		s[i] = s[i - 1] + a[i];
	}
	for(int i = 0; i <= n; ++ i) b[i] = s[i];
	discrete();
	add(query(0), 1);
	for(int i = 1; i <= n; ++ i)
	{
		int p = query(s[i]);
		dp[i] = ask(p);
		add(p, dp[i]);
	}
	printf("%d\n", dp[n]);
	return 0;
}