题解 | 计算数组的小和

#include <iostream>
#include<vector>
#define int long long
#define endl '\n'
using namespace std;

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

signed main() {
    cin>>n;
    arr.resize(n);
    help.resize(n);

    for(int &x:arr)cin>>x;
    int l=0,r=arr.size()-1;
    cout<<smallsum(l,r);
}
// 64 位输出请用 printf("%lld")