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

import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
     private static final int MAX = 100001;
    private static int n;
    private static int[] arr = new int[MAX];
    private static int[] help = new int[MAX];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != in.TT_EOF) {
            n = (int) in.nval;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            out.println(smallSum(0, n - 1));
            out.flush();
        }
        out.flush();
        out.close();
    }

    public static long smallSum(int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return smallSum(l, mid) + smallSum(mid + 1, r) + merge(l, mid, r);
    }

    public static long merge(int l, int mid, int r) {
        long ans = 0, sum = 0;
        for (int i = l, j = mid + 1; j <= r; j++) {
            while (i <= mid && arr[i] <= arr[j]) {
                sum += arr[i++];
            }
            ans += sum;
        }
        int a = l, b = mid + 1, i = l;
        while (a <= mid && b <= r) {
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= mid) {
            help[i++] = arr[a++];
        }
        while (b <= r) {
            help[i++] = arr[b++];
        }
        for (i = l; i <= r; i++) {
            arr[i] = help[i];
        }
        return ans;
    }
}