Luogu P1908逆序对

对于给定的一段正整数序列，逆序对就是序列中a_i > a_j 且 i<j 的有序对。注意序列中可能有重复数字。

输入格式

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。序列中每个数字不超过10⁹。

对于25%的数据，n≤2500。

对于50%的数据，n≤4 x 10⁴。

对于所有数据，n≤5 x 10⁵。

输出格式

输出序列中逆序对的数目。

输入
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]来说，它与前半部分数组中剩余的元素构成逆序对。