define _CRT_SECURE_NO_WARNINGS

include [HTML_REMOVED]

include [HTML_REMOVED]

long long guibing(int arr[], int tmp[], int l, int m, int r) {
int i = l;
int j = m + 1;
int k = l;
long long count = 0;
while (i <= m && j <= r) {
if (arr[i] <= arr[j]) {
tmp[k] = arr[i];
} else {
tmp[k] = arr[j];
count+=m-i+1;
}
}
while (i <= m) { // 修正了这里的循环条件和复制逻辑
tmp[k] = arr[i];
}
while (j <= r) { // 修正了这里的循环条件和复制逻辑
tmp[k] = arr[j];
}
for (int s = l; s <= r; s) { // 修正循环条件
arr[s] = tmp[s];
}
return count;
}
long long paixu(int arr[], int tmp[], int l, int r)
{
if(l<r)
{
int m = l + (r - l) / 2;
long long a = paixu(arr, tmp, l, m);
long long b = paixu(arr,tmp, m+1, r);
long long c = guibing(arr, tmp, l, m, r);
return a+b+c;
}
else
return 0;
}
int main()
{
int n = 0;
scanf(“%d”, &n);
int arr = (int)malloc(n * sizeof(int));
for (int i = 0; i < n; i)
{
scanf(“%d”, &arr[i]);
}
int tmp = (int)malloc(n * sizeof(int));

long long count =paixu(arr, tmp, 0, n-1);
printf(“%d”,count);

free(arr);
free(tmp);
return 0;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla