问题描述:给定序列(a1,…,an)。请求出这个序列中逆序对的总数。 输入格式: n a1 a2 … an 输出格式: 一个数T,表示逆序对的个数。 数据范围: 1<=n<=106。 -109 <=a1,…an<=109 注意:请用long long类型计数:T有可能超过int类型范围,用C语言实现
时间: 2024-03-16 08:46:37 浏览: 17
这道题目的解法和上一道题目是一样的,都是使用归并排序来处理逆序对问题。不过由于数据范围较大,需要使用 long long 类型来存储逆序对数目。下面是 C 语言的代码实现:
```c
#include <stdio.h>
typedef long long LL;
const int N = 1e6 + 10;
int n;
int q[N], tmp[N];
LL cnt;
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 (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else
{
tmp[k ++ ] = q[j ++ ];
cnt += mid - i + 1;
}
}
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];
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
merge_sort(0, n - 1);
printf("%lld\n", cnt);
return 0;
}
```
时间复杂度为 O(nlogn)。