题目描述
include[HTML_REMOVED]
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int q[N],tmp[N];
ll merge_sort(int *q,int l,int r){
if(l>=r)return 0;
int mid=l+r>>1;
ll res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[j]>=q[i])tmp[k]=q[i];
else{
tmp[k]=q[j];
res+=mid-i+1;
}
}
while(i<=mid)tmp[k]=tmp[i];
while(j<=r)tmp[k]=tmp[j];
for(int i=l,j=0;i[HTML_REMOVED]>n;
for(int i=0;i<n;i++)scanf(“%d”,&q[i]);
cout<<merge_sort(q,0,n-1);
return 0;
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla