P2344 奶牛抗议

2018-05-22 18:49:50


显然,如果一个区间 $[l,r]$ 能分成一组,则 $sum[r]>=sum[l-1]$

用 $f[i]$ 表示前i头奶牛的方案数,则

$f[i]=sigma(f[j], j<i $ && $ Sum(j+1,i)>=0 )$

然后直接这样做呢。。不一定能卡过

可以用树状数组优化:用 $c[x]$ 表示 $i$ 之前 $sum==x$ 的 $f$ 值之和

则 $f[i]$ 为小于 $sum[i]$ 的所有 $f$ 之和

进而可以求出小于 $sum[i]$ 的区间和

由于a数组有正有负,所以 $sum$ 可能为0

在树状数组中需要偏移一下(就是整体+1)

离散化一下也是可以的

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=1e9+9;
int n,a[N],cnt,sum[N],val[N],maxn=-2e9,c[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline int getpos(int x)
{
    return lower_bound(val,val+cnt+1,x)-val;
}
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,int k)
{
    ++x;
    while (x<=maxn+1)
    {
        c[x]=(c[x]+k)%mod; x+=lowbit(x);
    }
}
inline int getsum(int x)
{
    int res=0; ++x;
    while (x)
    {
        res=(res+c[x])%mod; x-=lowbit(x);
    }
    return res;
}
int main()
{
    n=read();
    for (reg int i=1;i<=n;i++)
    {
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
        maxn=max(maxn,sum[i]);
    }
    sort(sum,sum+n+1);
    for (reg int i=1;i<=n;i++)
      if (sum[i]!=sum[i-1]) val[++cnt]=sum[i];
    add(getpos(0),1); 
    int tot=0,ans=0;
    for (reg int i=1;i<=n;i++)
    {
        tot+=a[i];
        ans=getsum(getpos(tot))%mod;
        add(getpos(tot),ans);
    }
    printf("%d\n",ans);
    return 0;
}