题解 | 计算数组的小和

#include <iostream>
#include <vector>
using namespace std;
#define int long long
int arr[100005];

int merge(int l, int mid, int r) {
    int ans = 0;
    for (int j = mid + 1, sum = 0, i = l; j <= r; j++) {
        while(i <= mid && arr[i] <= arr[j]) {
            sum += arr[i++];
        }
        ans += sum;
    }
    int i = l, a = l, b = mid + 1;
    int help[100005];
    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;
}

int smallSum(int l, int r) {
    if (l == r) return 0;
    int mid = (l + r) / 2;
    return smallSum(l, mid) + smallSum(mid + 1, r) + merge(l, mid, r);
}

int32_t main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    cout << smallSum(1, n) << endl;

    return 0;
}