树状数组，python

解题思路:

注意事项:

参考代码:

n=int(input())

h=list(map(int,input().split()))

maxh=max(h)

cnt=[0]*(n)

c=[0]*(maxh+2)#c[i]代表的是身高i-1

def lowbit(i):

    return i&(-i)

def update(i,num):

    while(i<=maxh+1):

        c[i]+=num

        i+=lowbit(i)

def getsum(i):#计算的是原始数组[0,i]的和

    sum=0

    while(i>0):

        sum+=c[i]

        i-=lowbit(i)

    return sum

for i in range(n):#左边要统计比它大的

    update(h[i]+1,1)

    sum=getsum(h[i]+1)

    cnt[i]+=i+1-sum

c=[0]*(maxh+2)

for i in range(n-1,-1,-1):

    update(h[i]+1,1)

    sum=getsum(h[i])

    cnt[i]+=sum

ans=0

for i in range(len(cnt)):

    ans+=((1+cnt[i])*cnt[i]//2)

print(ans)