题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla#include [HTML_REMOVED]

int arr[100001];

int tmp[100001];

unsigned long count = 0;

void quick_sort_count(int* arr,int l,int r)
{
if(l>=r)
return;
int mid = l+r >> 1;
quick_sort_count(arr,l,mid);
quick_sort_count(arr,mid+1,r);

int i = l,j = mid+1, x = 0;

while(i<=mid && j<=r)
{
    if(arr[i]<=arr[j])
        tmp[x++] = arr[i++];
    else
    {
        tmp[x++] = arr[j++];
        count +=(mid-i+1);
    }
}
while(i<=mid)
{
    tmp[x++] = arr[i++];
}

while(j<=r)
{
    tmp[x++] = arr[j++];
}
for(int o = 0; o < x;o++)
    arr[l++] = tmp[o];
return;

}

int main()
{
int n;
scanf(“%d”,&n);
int i;
for(i=0;i<n;i++)
{
scanf(“%d”,&arr[i]);
}
quick_sort_count(arr,0,n-1);

printf("%ld",count);

return 0;

}