题解 | #计算数组的小和#

反向思路：从左往右，有多少个比当前元素a大的数，就产生多少个a的小和。

以1, 3, 5, 2, 4, 6为例，比1大的有5个元素，所以产生5个1小和，比3大的有3个，所以产生3个3的小和，即9，以此类推，5产生5，2产生4，4产生4，6产生0，所以数组小和为5+9+5+4+4+0=27

具体就是在归并排序时，if (arr[i] <= arr[j])时进行累加即可。

B站视频：链接，从1:01:25分开始食用。

import java.util.*;
import java.io.*;

public class Main{
    static int[] nums;
    //注意用long类型
    static long sum = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] arr = br.readLine().split(" ");
        nums= new int[N];
        for(int i=0; i < N; i++) {
            nums[i] = Integer.parseInt(arr[i]);
        }
        //归并排序
        mergeSort(0,N-1);
        //结果
        System.out.println(sum);
        //System.out.println(Arrays.toString(nums));
    }
    public static void mergeSort(int left,int right) {
        if(left < right) {
            int mid = (left + right) /2;
            mergeSort(left, mid);
            mergeSort(mid + 1, right);
            merge(left,mid,right);
        }
    }
    public static void merge(int left, int mid, int right) {
        int t = 0;
        int[] tmp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        while(i <= mid && j <= right) {
            if(nums[i] <= nums[j]) {
                //小和累加
                sum+=nums[i] * (right - j + 1);
                tmp[t++] = nums[i++];
            } else {
                tmp[t++] = nums[j++];
            }
        }
        while(i <= mid) tmp[t++] = nums[i++];
        while(j <= right) tmp[t++] = nums[j++];
        System.arraycopy(tmp, 0 , nums, left, tmp.length);
    }
}