DOs__lx @ 2020-02-23 13:05:49
只有50分 QWQ
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define re register
const int M=5e5+5;
int a[M],r[M],n;
long long ans;
namespace fir{
inline int read(){
int s=0,w=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-') w=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*w;
}
inline void write(int a){
int tot=abs(a);
if(a<0) putchar('-');
int cnt=0;
char c[M];
while(tot>0){
c[cnt++]=tot%10+'0';
tot/=10;
}
while(cnt>0) putchar(c[--cnt]);
}
}
namespace solve{
inline void msort(int s,int t){
if(s==t) return;
int mid=s+t>>1;
msort(s,mid);
msort(mid+1,t);
int i=s;
int j=mid+1;
int k=s;
while(i<=mid&&j<=t){
if(a[i]<=a[j]){
r[k]=a[i];
k++;
i++;
}
else{
r[k]=a[j];
k++;
j++;
ans+=(long long)mid-i+1;
}
}
while(i<=mid){
r[k]=a[i];
k++;
i++;
}
while(j<=t){
r[k]=a[j];
k++;
j++;
}
for(int i=s;i<=t;++i) a[i]=r[i];
}
}
int main(){
n=fir::read();
for(int i=1;i<=n;++i) a[i]=fir::read();
solve::msort(1,n);
fir::write(ans);
return 0;
}
by DOs__lx @ 2020-02-23 13:24:16
@WYXkk
by DOs__lx @ 2020-02-23 13:24:29
@我不是箭毒蛙
by DOs__lx @ 2020-02-23 13:24:45
@YCE3216037
by DOs__lx @ 2020-02-23 13:25:00
@Alpha
by DOs__lx @ 2020-02-23 13:25:23
蟹蟹了 各位大佬