逆序对

发表于 分类于 ， 阅读次数： 本文字数： 418 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
i64 merge_sort(int q[], int l, int r) {
  if (l >= r)
    return 0;

  int mid = l + r >> 1;

  i64 res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

  int k = 0, i = l, j = mid + 1;
  while (i <= mid && j <= r)
    if (q[i] <= q[j])
      tmp[k++] = q[i++];
    else {
      res += mid - i + 1;
      tmp[k++] = q[j++];
    }
  while (i <= mid)
    tmp[k++] = q[i++];
  while (j <= r)
    tmp[k++] = q[j++];

  for (i = l, j = 0; i <= r; i++, j++)
    q[i] = tmp[j];

  return res;
}