zzf12345666 @ 2023-03-27 20:58:07
import java.util.*;
public class 逆序对 {
static int N=100010;
static int [] q=new int[N];
static int [] temp=new int[N];
static int n;
static long ans=0;
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
n=in.nextInt();
for(int i=0;i<n;i++){
q[i]=in.nextInt();
}
System.out.println(merge(0,n-1));
}
static long merge(int l,int r){
if(l>=r){
return 0;
}
int mid=(l+r)/2;
ans=merge(l,mid)+merge(mid+1,r);
int i=l;int k=0;int j=mid+1;
while(i<=mid&&j<=r){
if(q[i]<=q[j]){
temp[k++]=q[i++];
}
else {
temp[k++]=q[j++];
ans+=mid-i+1;
}
}
while(i<=mid){
temp[k++]=q[i++];
}
while(j<=r){
temp[k++]=q[j++];
}
for(int z=l,y=0;z<=r;z++,y++){
q[z]=temp[y];
}
return ans;
}
}
by ACtheQ @ 2023-07-11 19:11:00
用c艹似乎可刑。