题解 | #计算数组的小和# Go实现

package main

import (
	"fmt"
)

func main() {
    var arr []int
    var n, tmp int
    fmt.Scan(&n)
    for i := 0; i < n; i++ {
        fmt.Scan(&tmp)
        arr = append(arr, tmp)
    }
    fmt.Println(Process(arr, 0, len(arr)))
}

// Process [l, r)
func Process(arr []int, l int, r int) int {
	if l+1 >= r {
		return 0
	}
	mid := l + (r-l)>>1
	return Process(arr, l, mid) + Process(arr, mid, r) + merge(arr, l, r)
}

// merge [l, r)
func merge(arr []int, l int, r int) (sum int) {
	var help []int
	mid := l + (r-l)>>1
	i, j := l, mid
	for i < mid && j < r {
		if arr[i] <= arr[j] {
            sum += (r - j) * arr[i]
			help = append(help, arr[i])
			i++
		} else {
			help = append(help, arr[j])
			j++
		}
	}

	for i < mid {
		help = append(help, arr[i])
		i++
	}
	for j < r {
		help = append(help, arr[j])
		j++
	}

	// copy help to arr
	copy(arr[l:r], help)
    return sum
}