反转计数给出大输入的错误

Question

给定代码是用于计算给定数组中的反转，或者我们可以说要计算数组中要进行的更改数量，以便将其分类。 代码对低于10 ** 5的输入工作正常，但是在此之前，我无法解决错误。 我还使用需要长的长数据类型，以便它可以处理大型输入。

 long long merge(long long arr[], int low, int mid, int high){
    long long count = 0;
    int l1 = mid-low+1;
    int l2 = high - mid;
    long long arr1[l1];
    long long arr2[l2];

    for(int i=0;i<l1;i++){
        arr1[i] = arr[low+i];
    }
    for(int i=0;i<l2;i++){
        arr2[i] = arr[mid+1+i];
    }

    int i=0, j=0, k=low;
    while(i!=l1 and j!=l2){
        if(arr1[i]<arr2[j]){
            arr[k++] = arr1[i++];
        }
        else{
            count+=l1-i;
            arr[k++] = arr2[j++];
        }
    }
    while(i<l1)
        arr[k++] = arr1[i++];
    while(j<l2)
        arr[k++] = arr2[j++];
    
    return count;
}

long long mergesort(long long arr[], int low, int high){
    long long count = 0;
    if(low<high){
        int mid = (low+high)/2;

        count+=mergesort(arr, low, mid);
        count+=mergesort(arr, mid+1, high);
        count+=merge(arr, low, mid, high);
    }
    return count;
}

long long solve(long long *arr, int n){
    if(n==1) return 0;
    return mergesort(arr,0, n);
}

Answer 1

合并函数正在使用本地堆栈空间用于可变长度阵列arr1 []，arr2 []，并用尽了大数组的堆栈空间。将代码合并为：

    long long * arr1 = new long long[l1];
    long long * arr2 = new long long[l2];
    // ...
    delete [] arr2;
    delete [] arr1;
    return count;     // existing code

但是，合并被称为大型数组，进行大量新闻和删除。最好是进行一次时间分配并将其复制到第二个数组，然后根据递归级别进行合并方向，如Wiki示例所示：

https://en.wikipedia.org/wiki/wiki/merge_sort#top-down_implementation

Answer 2

在这里，

long long arr1[l1];
long long arr2[l2];

您可以在堆栈上创建潜在的大型物品。在其他地方，您使用堆。您应该坚持使用堆