pypy3 解法, 执行用时: 1399ms, 内存消耗: 175884K, 提交时间: 2021-06-19 13:39:10

def lowbit(x):
    return x & -x


def add(k, x):
    i = k
    while i <= n:
        tr[i] += x
        i += lowbit(i)


def query(x):
    s = 0
    i = x
    while i:
        s += tr[i]
        i -= lowbit(i)
    return s


def get(x):
    l, r = 0, len(temp) - 1
    while l < r:
        mid = l + r >> 1
        if temp[mid] >= x:
            r = mid
        else:
            l = mid + 1 
    return l + 1


n = int(input())
arr = [0]
arr.extend(list(map(int, input().split())))
tr = [0] * (n + 5)
n+=1
for i in range(1, n ):
    arr[i] += arr[i - 1]
temp = list(set(arr))
temp.sort()

res = 0

for i in range(0, n):
    k = get(arr[i]) 
    res += query(k- 1)
#     print(k, res)
    add(k, 1)
print(res)

C++ 解法, 执行用时: 510ms, 内存消耗: 15992K, 提交时间: 2021-06-19 16:30:19

#include<iostream>
using namespace std;

const int N=1e6+5;
typedef long long LL;
LL h[N],ans,t[N];
int n,a;

void nxd(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    nxd(l,mid),nxd(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(h[i]>=h[j]) t[k++]=h[j++];
        else ans+=r-j+1,t[k++]=h[i++];
    }
    while(i<=mid) t[k++]=h[i++];
    while(j<=r) t[k++]=h[j++];
    for(j=0,i=l;i<=r;i++,j++) h[i]=t[j];
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
     cin>>a,h[i]=h[i-1]+a;
    nxd(0,n);
    cout<<ans;
    return 0;
}