题解 | 计算数组的小和

#include <iostream>
#include <cstdio>

using namespace std;

const int N=1e5+10;
int a[N], tmp[N];

long merge(int l, int mid, int r)
{
    long ans=0;
    for (int i=l, j=mid+1, sum=0; j<=r; j++)
    {
        while (i<=mid&&a[i]<=a[j]) sum+=a[i++];
        // 此处的sum不能更新为0，因为j到达一个新的位置必然i前面的数要加到sum里，如果sum更新那么i之前的数就相当于没加到sum中

        ans+=sum;
    }

    int i=l, j=mid+1, k=0;
    while (i<=mid&&j<=r)
        if (a[i]<=a[j]) tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
    while (i<=mid) tmp[k++]=a[i++];
    while (j<=r) tmp[k++]=a[j++];

    for (int i=l, j=0; i<=r; i++, j++) a[i]=tmp[j];

    return ans;
}

long fun(int l, int r)
{
    if (l==r) return 0;

    int mid=(l+r)/2;
    return fun(l, mid)+fun(mid+1, r)+merge(l, mid, r);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);

    long ans=fun(0, n-1);
    cout << ans << endl;

    return 0;
}