第四题代码，ac

import java.util.Scanner;

public class Netease4 {
  private static long count = 0;
  //辅助归并排序的数组
  private static int[] helper;
  //用来存位置信息
  private static int[] oldIndex;
  //类似于helper数组的问题辅助oldIndex数组的
  private static int[] oldIndex2;

  /**
   * 跟归并求逆序对个数一样的思路，只是存储了每个数关于索引位置的信息来计算
   * @param args
   */
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int[] nums = new int[n];
    helper = new int[n];
    oldIndex = new int[n];
    oldIndex2 = new int[n];

    for (int i = 0; i < n; i++) {
      nums[i] = sc.nextInt();
      oldIndex[i] = i;
      oldIndex2[i] = i;
    }

    mergeSort(nums, 0, n - 1);

    System.out.print(count);
  }

  private static void mergeSort(int[] nums, int low, int high) {
    if (high - low == 1) {
      if (nums[low] > nums[high]) {
        count++;
        swap(nums, low, high);
        swap(oldIndex, low, high);
        swap(oldIndex2, low, high);
      }
      return;
    }

    if (high == low) {
      return;
    }

    int mid = low + (high - low) / 2;

    mergeSort(nums, low, mid);
    mergeSort(nums, mid + 1, high);

    int index1 = mid, index2 = high, i = high;
    for (i = high; i >= low; i--) {

      if (index1 < low || index2 < mid + 1) {
        break;
      }

      if (nums[index1] <= nums[index2]) {
        helper[i] = nums[index2];
        oldIndex2[i] = oldIndex[index2];
        index2--;
      }else {
        helper[i] = nums[index1];

        for (int j = mid + 1; j <= index2; j++) {
          count += oldIndex[j] - oldIndex[index1];
        }

        oldIndex2[i] = oldIndex[index1];
        index1--;
      }
    }

    //如果哪边没用完
    if (index1 >= low) {
      while (index1 >= low) {
        helper[i] = nums[index1];
        index1--;
        i--;
      }
    }else {
      while (index2 >= mid + 1) {
        helper[i] = nums[index2];
        oldIndex2[i] = oldIndex[index2];
        index2--;
        i--;
      }
    }

    for (int j = low; j <= high; j++) {
      nums[j] = helper[j];
      oldIndex[j] = oldIndex2[j];
    }
  }

  private static void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
  }
}
/*
5
2 3 4 2 5

5
3 1 4 2 5

5
3 2 4 1 5

9
3 1 4 2 5 2 6 7 8
 */