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

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
long long ans;
//归并排序
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 ++];
ans += mid - i + 1; //统计逆序对
}
}
while (i <= mid) tmp[k ++] = a[i ++];
while (j <= r) tmp[k ++] = a[j ++];
for (int i = l, j = 0; i <= r; i ++, j ++) a[i] = tmp[j];
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
merge_sort(0, n - 1);
cout << ans << endl;
return 0;
}