AGC009C Division into Two

lINK
不妨认为(A>B)。
首先判一下无解。
设(f_i)表示(A)集合最后选第(i)个数的方案数。
转移的话枚举一下从哪个(j)转移过来。
显然(j)需要满足以下条件：
(j<i)
(S_j<S_i-A)
(forall a,bin(j,i)wedge a<b,S_a<S_b-B)
不难发现(j)的取值范围是一个区间，前缀和优化即可。

#include<cstdio>
#include<cctype>
#define ll long long
ll read(){ll x=0;int c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
const int N=100007,P=1000000007;
int inc(int a,int b){return a+=b,a>=P? a-P:a;}
int dec(int a,int b){return a-=b,a<0? a+P:a;}
int mul(int a,int b){return 1ll*a*b%P;}
ll a[N],f[N],sum[N];
int main()
{
    ll n=read(),A=read(),B=read(),i,l,r,ans=0;
    if(A<B) A^=B^=A^=B;
    for(i=1;i<=n;++i) a[i]=read();
    for(i=1;i+2<=n;++i) if(a[i+2]-a[i]<B) return puts("0"),0;
    f[0]=sum[0]=1,a[n+1]=B+a[n];
    for(i=1,l=r=0;i<=n;++i)
    {
        while(r<i&&a[i]-a[r+1]>=A) ++r;
        if(l<=r) f[i]=inc(f[i],dec(sum[r],l?sum[l-1]:0));
        sum[i]=inc(sum[i-1],f[i]);
        if(i>1&&a[i]-a[i-1]<B) l=i-1;
    }
    for(i=n;~i;--i)
    {
        ans=inc(ans,f[i]);
        if(a[i+1]-a[i]<B) break;
    }
    printf("%d",ans);
}