题目描述

原题

题目大意&链接

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。（逆序对：i < j 但 q[i] > q[j]，<i, j> 构成一个逆序对）

输入输出样例：
输入:

6
2 3 4 5 6 1

输出：

5

详情：ac_788逆序对的数量

解题思路

利用到归并排序的分治思想，递归排序的自顶向下过程中，统计3种情况的逆序对数量。
示意图

  1. 统计红色区间的逆序对数量： 
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
  2. 统计蓝色区间的逆序对数量： 
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
  3. 统计mid两边的逆序对数量： 
    //归并过程并计数逆序对
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else
        {
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    }

完整代码

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
int q[N], tmp[N];

LL merge_sort(int l, int r)
{
    if(l >= r) return 0;
    
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    
    //归并过程并计数逆序对
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else
        {
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    }
    
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    printf("%lld", merge_sort(0, n - 1));
    return 0;
}

时间和空间复杂度

时间复杂度：O(nlogn)
空间复杂度：O(n) 开辟了长度为n的temp数组