P2344 奶牛抗议

题目背景

Generic Cow Protests, 2011 Feb

题目描述

约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字可正可负。

约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。

约翰想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。

输入输出格式

输入格式：

• 第一行：单个整数N，1 ≤ N ≤ 100000

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

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

离散化+树状数组，

f[i] 为到第 i 只奶牛有几种分组

f[i]=∑j f[j](Sum[i]>=Sum[j])

f[i] = 所有的sum[j]（s[j]<=sum[i]）,将所有小于sum[i]的所有sum[j]加起来，每次需要把f[i]插入到树状数组中，所以树状数组刚好可以维护。

注意I64d与lld的使用。首先将f[0]插入，f[0] = 1;

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define LL long long
 4 
 5 using namespace std;
 6 const int MAXN = 100100;
 7 const int mod = 1000000009 ;
 8 struct Cow{
 9     LL sum;
10     int p;
11     bool operator < (const Cow &a) const 
12     {
13         return sum < a.sum;
14     }
15 }a[MAXN];
16 int p[MAXN],n;
17 LL sum[MAXN];
18 int lowbit(int x)
19 {
20     return x&(-x);
21 }
22 void update(int x,LL w)
23 {
24     while (x<=n)
25     {
26         sum[x] = (sum[x]+w)%mod;
27         x += lowbit(x);
28     }
29 }
30 LL query(int x)
31 {
32     LL ans = 0;
33     while (x)
34     {
35         ans = (ans+sum[x])%mod;
36         x -= lowbit(x);
37     }
38     return ans;
39 }
40 int main()
41 {
42     scanf("%d",&n);
43     for (int i=1; i<=n; ++i)
44     {
45         LL w;
46         scanf("%lld",&w);
47         a[i].sum = a[i-1].sum + w;
48         a[i].p = i;
49     }
50     a[n+1].sum = 0;
51     a[n+1].p = n+1;
52     sort(a+1,a+n+2);
53     int num = 0;
54     for (int i=1; i<=n+1; ++i)
55     {
56         if (i==1||a[i].sum!=a[i-1].sum) ++num;
57         p[a[i].p] = num;
58     }
59     update(p[n+1],1);
60     LL tmp = 0;
61     for (int i=1; i<=n; ++i)
62     {
63         tmp = query(p[i]);
64         update(p[i],tmp);
65     }
66     printf("%lld",tmp);
67     return 0;
68 }