快速排序
题目 Luogu P1177 将读入的 N 个数从小到大排...
Luogu P1908逆序对
对于给定的一段正整数序列,逆序对就是序列中ai > aj 且 i<j 的有序对。注意序列中可能有重复数字。
第一行,一个数n,表示序列中有n个数。
第二行n个数,表示给定的序列。序列中每个数字不超过109。
对于25%的数据,n≤2500。
对于50%的数据,n≤4 x 104。
对于所有数据,n≤5 x 105。
输出序列中逆序对的数目。
输入
6
5 4 2 6 3 1
输出
11
#include <iostream>
using namespace std;
typedef long long LL;
int n, a[5000010], b[5000010];
LL res = 0;
void reverse_pair(int l, int r){
if(l >= r) return;
int mid = (l + r) >> 1;
reverse_pair(l, mid);
reverse_pair(mid + 1, r);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r)
if(a[i] <= a[j]) b[k++] = a[i++];
else b[k++] = a[j++], res += mid - i + 1;
while(i <= mid) b[k++] = a[i++];
while(j <= r) b[k++] = a[j++];
for(i = l; i <= r; i++) a[i] = b[i];
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
reverse_pair(0, n - 1);
cout << res;
return 0;
}
解释 of 'res += mid - i + 1': 当合并两个有序数组时,如果a[i]>a[j],说明a[i]及其后面的元素都比a[i]大,因为数组是有序的。所以,对于当前的a[j]来说,它与前半部分数组中剩余的元素构成逆序对。