题目描述

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000

样例

输入
6
2 3 4 5 6 1
输出
5

go

归并排序

package main
import "fmt"
var res int
func mergeSum(q []int,l,r int)int{
    if l>=r{
        return 0
    }
    mid := (l+r)>>1
    res = mergeSum(q,l,mid)+mergeSum(q,mid+1,r)
    // 归并
    i,j :=l,mid+1
    var tmp []int
    for i<=mid && j<=r{
        if q[i]<=q[j]{
            tmp = append(tmp,q[i])
            i++
        }else{
            tmp = append(tmp,q[j])
            j++
            res += mid-i+1
        }
    }
    for i<=mid{
        tmp = append(tmp,q[i])
        i++
    }
    for j<=r{
        tmp = append(tmp,q[j])
        j++
    }
    i,j=l,0
    for i<=r{
        q[i] = tmp[j]
        i++
        j++
    }

    return res
}
func main(){
    var n int
    fmt.Scanf("%d",&n)
    q:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scanf("%d",q[i])
    }
    res:=mergeSum(q,0,n-1)
    fmt.Println(res)
    return
}

时间复杂度$O(nlogn)$

y总