题解 | 计算数组的小和 归并分治

#include <iostream>//O(NlogN)
using namespace std;
int a[100005],t[100005],n;
long long mergesort(int l,int m,int r){
    long long ans=0,sum=0;
    for(int i=l,j=m+1;j<=r;j++){
        while(i<=m&&a[j]>=a[i]){
            sum+=a[i++];
        }
        ans+=sum;
    }
    int i=l,j=m+1,ti=l;
    while(i<=m&&j<=r){
        if(a[i]<a[j])t[ti++]=a[i++];
        else t[ti++]=a[j++];
    }
    while(i<=m)t[ti++]=a[i++];
    while(j<=r)t[ti++]=a[j++];
    for(int i=l;i<=r;i++)a[i]=t[i];
    return ans;
}
long long smallsum(int l,int r){
    if(l==r)return 0;
    int m=(l+r)/2;
    return smallsum(l, m)+smallsum(m+1,r)+mergesort(l,m,r);
}
int main() {
   cin>>n;
   for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
   }
   cout<<smallsum(0,n-1);
   return 0;
}

【算法讲解022【必备】归并分治】 https://www.bilibili.com/video/BV1L14y1B7ef/?share_source=copy_web&vd_source=5065fa61022691e8df35c771a30e6d29