输入 第一行是一个整数N，代表序列长度。 第二行包含N个整数，a[1], a[2], ..., a[N]，代表序列中的元素。 输出 显示序列中含有的逆序对的个数。 样例输入 4 2 4 1 7 样例输出 2代码实现

#include <iostream>
using namespace std;

const int N = 1e5+10;

int n;
int a[N], tmp[N];
long long res;

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

int mid = (l + r) >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);

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

while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];

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

int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];

merge_sort(0, n - 1);

cout << res << endl;

return 0;
}