给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000

输入样例：

6
2 3 4 5 6 1

输出样例：

5

题解：

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
int q[N], temp[N];
long ans;

void merge_sort(int q[], int l, int r){
	//递归终止条件
    if (l >= r) return;
    //确定分界点
    int mid = l + r >> 1;
    //递归排序
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    //归并--->合二为一
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r){
        if (q[i] <= q[j]) temp[k++] = q[i++];
        else{
            ans =  ans + mid - i + 1;
            temp[k++] = q[j++];
        } 
    }
    			//扫尾
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];
    			//把归并后的序列复制到原序列中
    for (i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];
}

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

思路：

一看到这个题我就感觉似曾相识，知道需要使用排序>归并排序的思想来做，于是特地整理了一遍，见博客排序>归并排序。

在排序>归并排序的归并步骤时，可以顺便统计逆序对的个数。

假设正在归并上面的数组，左侧的2，3，6，8和右侧的1，4，5，7已经排好序了，左侧和右侧内部都没有逆序对，而从左侧取一个数，从右侧取一个数，则有可能形成逆序对。

例如，开始左侧拿出2，右侧拿出1，可知2>1，形成了逆序对。此时逆序对只是加1吗？并不是，因为2右边的数都是大于2的，所以可以判断左边的数和右边的1可以形成4对逆序对（(2,1)、(3,1)、(6,1)、(8,1)）。

接下来比2和4，不会形成逆序对。再比3和4，不会形成逆序对。

当比较到6和4的时候，形成了逆序对，个数为2((6,4)、(8,4))。

归纳一下，也就是在归并的时候，如果右侧的元素小于左侧的元素，这个时候开始统计逆序对就行了，如果左侧的索引为i，左侧的末尾元素的索引为mid，逆序对个数就为mid - i + 1。

这样并没有结束，前面的假设是左侧和右侧是有序的，事实上并不是，左侧和右侧也进行了归并的过程才能变得有序，而在归并过程中，也能计算出逆序对的个数。

所以：

总的逆序对的个数=左侧归并时求得的逆序对个数 + 右侧归并时求得的逆序对个数 + 对整体进行归并时的逆序对个数。

可能会怀疑这三种情况会有重复，但是并没有。左侧归并找到的逆序对相当于从左侧数组中取2个数，而整体归并的时候是分别从左右数组中取1个数，不可能发生重复！

思路转至链接。

答案范围：
当我们的输入样例是一个降序数组5 4 3 2 1

逆序对的数量ans

=n−1+n−2+n−3+…+1=n−1+n−2+n−3+…+1
=n∗(n−1)/2=n∗(n−1)/2
n=1e5n=1e5
ans=5e9 > INT_MAX=1e9

所以

res 为long long类型