Anakin @ 2019-10-02 13:46:10
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define MAXN 500000+10
using namespace std;
inline int read(){
int out=0;
char c=getchar();
while(c<48||c>57) c=getchar();
while(c<=57&&c>=48){
out=(out<<1)+(out<<3)+c-48;
c=getchar();
}
return out;
}
inline void write(ll x){
if(x>9) write(x/10);
putchar(x%10+48);
}
int a[MAXN];
ll ans;
void Merge(int a[],int l,int mid,int r){
int len=r-l+1;
int *temp=new int[len];
int i=1,j=mid+1;
int cnt=0;
while(i<=mid&&j<=r){
if(a[i]<=a[j]){
temp[cnt++]=a[i++];
}
else{
ans+=mid-i+1;
temp[cnt++]=a[j++];
}
}
for(;i<=mid;++i){
temp[cnt++]=a[i];
}
for(;j<=r;++j){
temp[cnt++]=a[j];
}
for(int k=0;k<len;++k){
a[l+k]=temp[k];
}
}
void Mergesort(int a[],int l,int r){
if(l<r){
int mid=(l+r)>>1;
Mergesort(a,l,mid);
Mergesort(a,mid+1,r);
Merge(a,l,mid,r);
}
}
int main(){
int n=read();
for(int i=1;i<=n;++i){
a[i]=read();
}
Mergesort(a,1,n);
write(ans);
return 0;
}
by 火车司机 @ 2019-10-02 13:57:41
@Anakin
by BFqwq @ 2019-10-02 14:00:49
赋值的锅,应该是从l开始而不是1