已调2hour+

求大佬帮帮忙吧（自己的数据测出来没问题，洛谷WA on#2#7#9#10）

其中#2本地跑出来1465901，洛谷跑出来2???????

#include<bits/stdc++.h>
using namespace std;
long long int n,a[100001],t[100001],f[100001],su[100001],summ,MOD=1000000009;
struct node
{
	long long int a,b;
	friend bool operator<(node c,node d)
	{
		return c.a<d.a;
	}
}sum[100001];
long long int inline lb(long long int x)
{
	return x&(-x);
}
void inline in(long long int x,long long int y)
{
	y%=MOD;
	while(x<=n+1)
	{
		t[x]+=y%MOD;
		t[x]%=MOD;
		x+=lb(x);
	}
}
long long int inline q(long long int x)
{
 	long long int ans=0;
	while(x>0)
	{
		ans+=t[x]%MOD;
		ans%=MOD;
		x-=lb(x);
	}
	return ans%MOD;
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
  cin>>a[i];
  sum[i].b=i;
  sum[i].a=sum[i-1].a+a[i];
  }
  sort(sum+1,sum+n+1);
  for(int i=1;i<=n;i++)
  su[sum[i].b]=i;
  for(int i=1;i<=n;i++)
  {
  	summ+=a[i];
  	f[i]=q(su[i])%MOD;
  	if(summ>=0)
  	f[i]++;
  	f[i]%=MOD;
  	//cout<<i<<" "<<f[i]<<" "<<su[i]<<endl;
  	in(su[i],f[i]);
  }
  cout<<f[n]%MOD<<endl;
}