NOIP 提高 2017 第一轮 第 25 题：归并排序统计逆序对

题目

```
#include <iostream>
using namespace std;
int n, s, a[100005], t[100005], i;
void mergesort(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) / 2;
    int p = l;
    int i = l;
    int j = mid + 1;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    while (i <= mid && j <= r)
    {
        if (a[j] < a[i])
        {
            s += mid - i + 1;
            t[p] = a[j];
            p++;
            j++;
        }
        else
        {
            t[p] = a[i];
            p++;
            i++;
        }
    }
    while (i <= mid)
    {
        t[p] = a[i];
        p++;
        i++;
    }
    while (j <= r)
    {
        t[p] = a[j];
        p++;
        j++;
    }
    for (i = l; i <= r; i++)
        a[i] = t[i];
}
int main()
{
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    mergesort(1, n);
    cout << s << endl;
    return 0;
}
```
输入：6       
2 6 3 4 5 1   
输出：_________

请写出程序的输出结果。

答案

8

题解

考点定位

本题考「归并排序逆序对」,对应大纲 4.3.2 归并（难度【4】）。

解题过程

mergesort 中 a[j]<a[i] 时 s += mid−i+1（统计逆序对）。输入 2,6,3,4,5,1：逆序对 (6,3),(6,4),(6,5),(6,1),(3,1)? 逐对：(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1) → 8 个。

答案：8。

易错提醒

① 归并时右半元素先出 ⇒ 它比左半剩余的都小 ⇒ s+=mid−i+1；② 逆序对数验证：暴力 O(n²) 数一遍对照。