计算数组的小和

// 结果过大会导致整型溢出，注意要用long long类型
#include <stdio.h>
#include <stdlib.h>

long long minSum(int *arr, int l, int r);

long long merge(int *arr, int l, int m, int r);

int main(void) {
    int *arr, n;
    scanf("%d", &n);
    arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    printf("%ld\n", minSum(arr, 0, n - 1));
    return 0; 
}

long long minSum(int *arr, int l, int r) {
    if (l == r)
        return 0;
    int m = (l + r) / 2;
    return minSum(arr, l, m) 
        + minSum(arr, m + 1, r) 
        + merge(arr, l, m, r);
}

long long merge(int *arr, int l, int m, int r) {
    int n = r - l + 1;
    int *help = (int *) malloc(n * sizeof(int));
    int index = 0;
    
    int p1 = l, p2 = m + 1;
    long long sum = 0;
    while (p1 <= m && p2 <= r) {
        if (arr[p1] <= arr[p2]) {
            sum += (r - p2 + 1) * arr[p1];
            help[index++] = arr[p1++];
        } else {
            help[index++] = arr[p2++];
        }
    }
    while (p1 <= m) {
        help[index++] = arr[p1++];
    }
    while (p2 <= r) {
        help[index++] = arr[p2++];
    }
    for (int i = 0; i < n; i++) {
        arr[l + i] = help[i];
    }
    return sum;
}