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

//小和问题可以转化成求某个数右边大于等于他的数的个数乘当前这个数
//而求某个数右边有多少个大于等于他的数可以使用使用归并排序解决
#include<bits/stdc++.h>
//该递归函数的含义为在arr数组上从left到right排好序并且返回小和的大小
long long func(long long *arr,int left,int right);
//merge函数的含义为把arr数组的左半区和右半区合并成一个整体有序的数组，并且返回小和大小
long long merge(long long *arr,int left,int mid,int right);
using namespace std;
int main(){
    int n;
    cin>>n;
    long long *p=new long long[n];
    for(int i=0;i<n;i++)
        cin>>p[i];
     cout<<func(p, 0, n-1);
    return 0;
    }
//归并排序的思想为，对从left到right排好序
//先找中间位置mid，让left到mid先有序再让mid到right有序
//最后再把两段有序数组merge到一起
long long func(long long *arr,int left,int right)
{
    //base case
    if(arr==NULL||left==right)//当数组为空或者数组中只有一个元素时，此时已经有序且小和为0
    {
        return 0;
    }
    else{
        int mid=((right-left)/2+left);//中间位置，防溢出处理
        return func(arr, left, mid)+func(arr, mid+1, right)+merge(arr, left, mid, right);
    }
}
long long merge(long long  *arr,int left,int mid,int right){
    if(arr==NULL||left==right)
        return 0;//小和为0
    int help[right-left+1];//辅助数组
    long long L=left,R=mid+1;
    long long res=0;//小和大小
    int index=0;//给help数组使用
    while(L<=mid&&R<=right){
        if(arr[L]<=arr[R]){//当左半区的数小于右半区的数此时产生小和
            res+=(right-R+1)*arr[L];
            help[index++]=arr[L++];
        }
        else{
            help[index++]=arr[R++];
        }
    }
    while(L<=mid){
        help[index++]=arr[L++];
    }
    while(R<=right){
        help[index++]=arr[R++];
    }
    //将help数组里的东西拷贝到arr数组中去完成排序
    for(int i=0;i<index;i++){
        arr[left+i]=help[i];
    }
    return res;
}