2658-【USACO-2011-FEB-金组】Generic Cow Protests

求方案数，先从$DP$角度思考，假设$dp[i]$表示以$i$为结尾符合要求的方案数。类似最长非降子序列思考方式，能够转移的情况为：

其中转移条件为$sum[j]<=sum[i]$，$sum$表示前缀和。
但是时间复杂度为$O(n^2)$。
仔细分析，主要转移需要枚举，时间复杂度高了。
注意转移条件$sum[j]<=sum[i]$，满足这个条件的不就是逆序对么(从大到小的角度考虑，前面小后面大为逆序对)。
计算逆序对可以用树状数组解决，但是前缀和$sum$，有可能是负数，也有可能会很大，所以需要离散化处理。
还有一个特殊情况需要考虑。$sum[i]>=0$，表示$sum[i]$本身可以看成一组（即不划分），所以需要把和为$0$考虑进去，对和大于等于0的进行初始化，不然就漏情况了。
结构体设计

struct node{
	LL sum;
	int id;
	bool operator < (const node& rhs) const{
		return sum < rhs.sum;
	}
}a[mx];

LL是long long 简写，mx表示题中最大个数。
前缀和处理

	for(int i = 1; i <= n; i++){
		int x;
		cin>>x;
		a[i].sum = a[i-1].sum + x;
		a[i].id = i;
	}

离散化处理

	a[n+1].sum = 0;
	a[n+1].id = n + 1;
	sort(a+1,a+n+2);
	int new_id = 0;
	for(int i = 1; i <= n + 1; i++){ //离散化
		if(i==1 || a[i].sum!=a[i-1].sum) new_id++;
		p[a[i].id] = new_id;
	}

记得要把0加入进去排序。
初始化&动归计算（逆序对）
初始化不能忘记，类似动规的初始化。

	add(p[n+1],1); //所有大于0的前缀和初始化为1
	LL ans = 0;
	for(int i = 1; i <= n; i++){ //按输入顺序扫描
		ans = query(p[i]);       //计算逆序对数量
		add(p[i],ans);           //转移
	}

树状数组维护

void add(int i, LL d)
{
	for(;i<=n+1;i += i & -i){
		dp[i] = (dp[i] + d) % MOD;
	}
}

树状数组求和

LL query(int i)
{
	LL s = 0;
	for(;i > 0; i -= i & -i){
		s = (s + dp[i]) % MOD;
	}
	return s;
}

总的来说利用树状数组可以快速查询的功能实现动归转移。