题目描述

blablabla

样例

#本质还是找逆序对，树状数组是找在某个数前面有多少个比他大的 后面有多少比他小的
#构成这个数的逆序对 这里把身高作为原数组中的下标
n = int(input())
N = 1000010
w = [0]*N
tr = [0]*N
sum = [0]*N
w[1:] = list(map(int,input().split()))

def lowbit(x):
    return x&(-x)

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

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

for i in range(1,n+1):
    w[i] += 1 
    sum[i] += query(N-1) - query(w[i])
    add(w[i],1)

tr = [0]*N

for i in range(n,0,-1):
    sum[i] += query(w[i]-1)
    add(w[i],1)

res = 0
for i in range(1,n+1):
    res += (sum[i] * (sum[i]  + 1))//2
print(res)
#归并
n = int(input())
a = list(map(int,input().split()))
cont = [0] * 100010
q = []
for i in range(n):
    q.append((a[i],i))
def mergesort(l,r,q):
    if l >= r:
        return 0
    mid = l + r >> 1
    mergesort(l,mid,q)
    mergesort(mid + 1,r,q)
    i,j = l,mid + 1
    temp = []
    while i <= mid and j <= r:
        if q[i] <= q[j]:
            temp.append(q[i])
            cont[q[i][1]] +=  j - mid - 1 
            i += 1 
        else:
            temp.append(q[j])
            cont[q[j][1]] += mid - i + 1 
            j += 1 
    while i <= mid:
        cont[q[i][1]] += j - mid - 1
        temp.append(q[i])
        i += 1 
    temp += q[j:r +  1 ]
    q[l : r +1 ] = temp
mergesort(0,n-1,q)
res = 0
for i in range(n):
    res += (cont[i] * (cont[i] + 1 )) // 2
print(res)

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla