题解 | #逆序数#

package main

import (
    .    "fmt"
    "os"
    "io"
    "bufio"
)
var cnt int
var tmp []int
func mergeSort(arr []int, l, r int) {
    if l < r {
        m := l + (r -l)/2
        mergeSort(arr,l,m)
        mergeSort(arr,m+1,r)

        ll,rr :=l,m+1
        for i := l; i <= r;i++{
            if ll <= m && (rr > r|| arr[ll] <= arr[rr]){
                tmp[i] = arr[ll]
                ll++
            }else {
                tmp[i] = arr[rr]
                cnt += m - ll + 1
                rr++
            }
        }
        for i := l; i<=r;i++{
            arr[i] = tmp[i]
        }
    }
}

// https://ac.nowcoder.com/acm/problem/15163
func NC15163(_r io.Reader, _w io.Writer) {
    in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
    defer out.Flush()
    
    var n int
    Fscan(in, &n)
    arr := make([]int, n)
    tmp = make([]int, n)
    for i := 0; i < n; i++ {
        Fscan(in, &arr[i])
    }
    mergeSort(arr, 0, n-1)
    Fprintln(out, cnt)
    
}

func main() {
    NC15163(os.Stdin, os.Stdout)
}