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

#include<iostream>
using namespace std;

const int MAXN = 100001;
int arr[MAXN];
int help[MAXN];
int n;
// 返回跨左右产生的小和累加和，左侧有序、右侧有序，让左右两侧整体有序
// arr[l...m] arr[m+1...r]
long long merger(int l,int m,int r)
{
    long long ans = 0; 
    for(int j=m+1, i = l, sum=0;j<=r; j++)
    {
        while(i<=m && arr[i]<=arr[j])
        {
            sum+=arr[i++];
        }
        ans+=sum;
    }
    //正常merger
    int  i = l;
    int a = l;
    int b = m+1;

    while(a<=m && b<=r)
    {
        help[i++] = arr[a] <= arr[b] ?arr[a++]:arr[b++];
    }
    while(a<=m)
    {
        help[i++] = arr[a++];
    }
    while(b<=r)
    {
        help[i++] = arr[b++];
    }
    for( i=l;i<=r;i++)
    {
        arr[i]= help[i];
    }
    return ans;
}
long long SmallSum(int l,int r)
{
    if(l==r)
    {
        return 0;
    }
    int m=((l+r)>>1);
    return SmallSum(l,m) + SmallSum(m+1,r)+merger(l,m,r);
}


int main()
{
    while(cin >> n)
    {
        for(int i= 0;i<n;i++)
        {
            cin >> arr[i];
        }
        cout<<SmallSum(0,n-1)<<endl;
    }

    return 0;
}