bingnoi @ 2021-03-17 22:44:57
#include<bits/stdc++.h>
using namespace std;
int number[500005];
int copy_array[5000005];
long long int ans=0;
int total;
//int read(){
// int acc=0,sign=1;
// char ch=getchar();
// while(ch<'0'&&ch>'9'){
// if(ch=='-'){
// sign=-1;
// ch=getchar();
// }
// }
// while(ch>='0'&&ch<='9'){
// acc=acc*10+ch-'0';
// ch=getchar();
// }
// return acc*sign;
//}
void msort(int left,int right){
printf("%d,%d\n",left,right);
if(left==right)
return;
int mid=(left+right)/2;
int reme_left=left;
int reme_right=mid+1;
int array_start=left;
msort(1,mid);
msort(mid+1,right);
while(reme_left<=mid&&reme_right<=right){
if(number[reme_left]<=number[reme_right])
copy_array[array_start++]=number[reme_left++];
else{
copy_array[array_start++]=number[reme_right++];
ans+=mid-reme_left+1;
}
}
while(reme_left<=mid)
copy_array[array_start++]=number[reme_left++];
while(reme_right<=right)
copy_array[array_start++]=number[reme_right++];
for(int m=left;m<=right;m++)
number[m]=copy_array[m];
}
int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&total);
for(int m=1;m<=total;m++){
scanf("%d",&number[m]);
}
msort(1,total);
printf("%lld",ans);
return 0;
}
by ud2_ @ 2021-03-17 23:09:17
@bingnoi
msort(1,mid);
by bingnoi @ 2021-03-18 10:28:38
@sjx233_ ?请问大佬什么意思
by ud2_ @ 2021-03-18 10:31:18
@bingnoi 这行错了。
by bingnoi @ 2021-03-18 12:13:57
@sjx233_ 大意了 谢谢