原题链接

https://www.acwing.com/problem/content/description/790/

逆序对.png

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int q[N],tmp[N];

LL merge_sort(int l, int r)
{
  if(l >= r) return 0;

  int mid = l + r >> 1;
  LL res = merge_sort(l, mid) + merge_sort(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
    {
      tmp[k ++] = q[j ++];
      //res是逆序对的数量，请看画图。
      res += mid - i + 1;
    }

  // 把剩下的数扔进tmp
  while(i <= mid) tmp[k ++] = q[i ++];
  while(j <= r) tmp[k ++] = q[j ++];

  //替换原序列
  for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];

  //返回逆序对的数量
  return res;
}
int main()
{
  cin >> n;
  for(int i=0;i<n;i++)
    cin >> q[i];

  cout << merge_sort(0, n-1) << endl;

  return 0;
}