/
1.逆序的定义巧妙的结合了归并排序,可利用归并排序的模板去做
2.对于一个已经排好顺序的左右部分数组,如果右边的某个数小于
坐标的某个数,那么左边这个数到数组的结尾的数的总个数就是右边
这个数的逆序对
3.注意数据范围,N=100010,最差的情况全是逆序数组,那么逆序对
个数是N(N-1)/2,超过JAVA中int范围,所以返回类型要用long
/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
static int N = 100010;
static int[] array = new int[N];
static int[] tmp = new int[N];
public static long mergeSort(int l, int r){
if(l >= r) return 0;
int mid = l + r >> 1;
long count = mergeSort(l, mid) + mergeSort(mid + 1, r);//无需初始化
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(array[i] <= array[j]) tmp[k++] = array[i++];//前半部分小于后面
else{//大于,构成逆序对
tmp[k++] = array[j++];
count += mid - i + 1;
}
}
while(i <= mid) tmp[k++] = array[i++];
while(j <= r) tmp[k++] = array[j++];
for(i = l, j = 0; i <=r ; i++, j++) array[i] = tmp[j];
return count;
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String[] arry = in.readLine().split(" ");
for(int i = 0; i < n; i++){
array[i] = Integer.parseInt(arry[i]);
}
long result = mergeSort(0, n-1);
System.out.print(result);
}
}