题目描述

blablabla

样例

blablabla

//在归并时候，进行技术，若左半边某个数大于右半边某个数，那左半边那个数及后面那个数都是大于右半边

include[HTML_REMOVED]

using namespace std;

typedef long long LL;

const int N=100001;
int q[N],tmp[N];

LL merge_sort(int a[],int left,int right)
{
if(left>=right)
{
return 0;
}
int mid=left+right>>1;
LL res=merge_sort(a,left,mid)+merge_sort(a,mid+1,right);
int left1=left,right1=mid;
int left2=mid+1,right2=right;
int i=left;
while(left1<=right1&&left2<=right2)
{
if(a[left1]<=a[left2])
{
tmp[i]=a[left1];
}
else
{
res+=right1-left1+1;
tmp[i]=a[left2];
}
}
while(left1<=right1)
{
tmp[i]=a[left1];
}
while(left2<=right2)
{
tmp[i]=a[left2];
}
for(int j=left;j<=right2;j++)
{
a[j]=tmp[j];
}
return res;
}

int main()
{
int n=0;
scanf(“%d”,&n);
for(int i=0;i<n;i++)
{
scanf(“%d”,&q[i]);
}
cout<<merge_sort(q,0,n-1)<<endl;
return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla