mimi301208's blog

By mimi301208, history, 2 months ago, In English

Is there any optimal solution (better than O(n^2) to count sub-arrays have non-negative sum?

I've try by using prefix sum and set to count the number of the subarray but it takes lots of time because time complexity of distance function is linear:

multiset <long long> a
for(int i=1;i<=n;++i)
    {
        cin>>tmp;
        sum[i]=sum[i-1]+tmp;
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        if(a.size()>0)
            {
            auto it = a.upper_bound(sum[i]);
            ans+=(distance(a.begin(),it;
        }
        if(sum[i]>=0)   ++ans;
        a.insert(sum[i]);
    }
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

You can do the same thing with an ordered set, and it improves "distance" (linear) to logarithmic.