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

#include <iostream>
#include <vector>
using namespace std;
long long merge(vector<int>& arr,vector<int>& help,int l, int m,int r)
{
    long long ans = 0;
    long long sum = 0;
    for(int j = m+1,i = l;j <=r;++j)
    {
        while(i<=m && arr[i] <= arr[j])
        {
            sum += arr[i++];
        }
        ans += sum;
    }

    int i = l;
    int a = l;
    int b = m+1;
    while(a<=m && b<=r)
    {
        if(arr[a] <= arr[b])
        {
            help[i++] = arr[a++];
        }
        else
        {
            help[i++] = arr[b++];
        }
    }

    while(a<=m)
    {
        help[i++] = arr[a++];
    }
    while(b<=r)
    {
        help[i++] = arr[b++];
    }

    for(int i = l;i<=r;++i)
    {
        arr[i] = help[i];
    }

    return ans;
}

long long SmallSum(vector<int>& arr,vector<int>& help,int l,int r)
{
    if(l == r)
    {
        return 0;
    }
     
     int m = (l+r)/2;
    
    return SmallSum(arr,help,l,m) + SmallSum(arr,help,m+1,r)+merge(arr,help,l,m,r);
}
int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;
    cin >> n; // 注意 while 处理多个 case
        vector<int> arr(n);
        vector<int> help(n);
        for(int i =0;i<n;++i)
        {
            cin>>arr[i];
        }
        cout<<SmallSum(arr,help,0,n-1);
    
}
// 64 位输出请用 printf("%lld")