求逆序数，用归并排序或者bst都可以。水题中的战斗机。。。。WA on case 12 无数次，百思不得其解，输入的范围已经考虑过了。。。。最后忍不住了，上网看看别人的答案，发现原来是输出的范围没有考虑，输出的范围是会超过int类型的，所以要用__int64。。。。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int a[65537];int b[65537];__int64 mergeSort(int a[], int start, int end) {  int len = end - start + 1;  assert(len > 0);  if (len == 1) {    return 0;  }  if (len == 2) {    if (a[start] > a[end]) {      swap(a[start], a[end]);      return 1;    } else {      return 0;    }  }  int mid = start + (end - start) / 2;  __int64 inversionNum = mergeSort(a, start, mid) + mergeSort(a, mid + 1, end);  int i = start;  int j = mid + 1;  int k = 0;  for (k = 0; k < len; ++k) {    if (i > mid) { b[k] = a[j]; ++j; continue; }    if (j > end) { b[k] = a[i]; ++i; continue; }    if (a[j] < a[i]) {      b[k] = a[j];      ++j;      inversionNum = inversionNum + (mid - i + 1);    } else {      b[k] = a[i];      ++i;    }  }  for (k = 0; k < len; ++k) {    a[start + k] = b[k];  }  return inversionNum;}int main() {  int N;  scanf("%d", &N);  int i;  for (i = 0; i < N; ++i) {    scanf("%d", &(a[i]));  }  printf("%I64d\n", mergeSort(a, 0, N - 1));  return 0;}