逆序对

逆序对的定义

假定有一个序列，对于序列中任意两个元素和，如果有，则称和是一对逆序对。我们接下来以洛谷P1908 逆序对为例，介绍求解逆序对数的求解方法。

题目简介

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ​ 且 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

解题思路

如果我们采用的暴力方法，这个题目会超时。则我们使用归并排序思想，具体可以查看这篇文章：归并排序。每次归并排序的时候，当我们前后两段数组进行比较并且插入到临时数组这个过程中时，如果有后段数组首元素小于前段数组首元素，必然存在逆序对，这些逆序对由前段数组和后段数组的首元素组成。

解题代码

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n;
long long ans;
int a[1000000];
int r[1000000];

void msort(int s, int t)
{
    if(s == t) return ;
    int m = (s + t) / 2;
    msort(s, m);
    msort(m+1, t);
    
    int i = s;
    int j = m+1;
    int k = s;
    while(i <= m && j <= t)
    {
        if(a[i] <= a[j]) r[k++] = a[i++];
        else
        {
            ans += m - i + 1;
            r[k++] = a[j++];
        }
    }
    while(i <= m) r[k++] = a[i++];
    while(j <= t) r[k++] = a[j++];
    for(int l=s; l<=t; ++l) a[l] = r[l];
}

inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) a[i] = read();
    msort(1, n);
    printf("%lld\n",ans);
    return 0;
} 

Note

• 这道题目建议使用较快的输入输出。