1439: 蓝桥杯历届试题-小朋友排队 python 时间超限

n = int(input())
a = list(map(int,input().strip().split()))
a.insert(0,0)
b = [0]*(n+1)
N = 1000000
def lowbit(x):
    return x&(-x)
def update(x ,val):   
    while(x<=N):
        tree[x] += val 
        x += lowbit(x)
def getsum(i):
    res = 0
    while(i>0):
        res += tree[i]
        i -= lowbit(i)
    return res 
tree = [0]*(N+1)
for i in range(1,n+1):
    b[i] += i-1 - getsum(a[i])
    update(a[i],1)
tree = [0]*(N+1)
for i in range(n,0,-1):
    b[i] += getsum(a[i]-1)
    update(a[i],1)
total = 0    
for i in range(1,n+1):
    total += int((1+b[i])*b[i]/2)
print(total)
时间超限了，原因未知，标记一下之后仔细想想