题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

int a[100010];
int temp[100010];
int n;
long long cun =0;

void merge_sort(int q[],int l,int r)
{
if(l>=r)return ;
int mid = (l + r) >>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int k =0,i = l, j =mid+1;
while(i<= mid && j <=r)
{
if(q[i]<=q[j])
{
temp[k] =q[i];

    }
    else
    {
        temp[k++] = q[j++];
          cun+=mid -i +1;
    }
}
while(i<=mid)
{
    temp[k++] = q[i++];

}
while(j<=r)temp[k++] =q[j++];
for(i=l,j=0;i<=r;i++,j++)q[i]=temp[j];

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

cout << cun<<endl;

}