题目描述

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] >a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。

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

数据范围
1≤n≤100000

样例

输入样例：
6
2 3 4 5 6 1

输出样例：
5

逆序对的定义：
如果下标 i < j < k,但是s[i]>s[j]>s[k];则(s[i],s[k]),(s[i],s[j]),(s[j],s[k])也都是逆序对，a[i]是可以使用多次的，
又想到逆序对可以分为3类，
将序列从中间分开：
1. 两个元素都在左边
2. 两个元素都在右边
3. 一个元素在左边，一个元素在右边

这道题大致算法框架：
1. 递归算左边的
2. 递归算右边的
3. 算一个左边的一个右边的
4. 把他们加到一块

这道题最重要的部分是：左右两边的元素在任何调换顺序的情况下并不影响第三步的进行，因此我们数完就给它排序，这么做的好处在于，序列已经排好序了，有利于第三步的计数，如果无序暴力数的话这一步是O(n^2)的。n<=1e5,n^2<=1e10，肯定会爆掉的

egg：
8 9 10 | 1 4 11
此序列左边的顺序和右边的顺序都是已经有序的，左边最左端最小的8 就> 1，8后面的数一定大于1，所以根本不用遍历9,10了，9,10绝对可以跟1构成逆序对，这就省了很多的时间，如果左边下标为i的元素大于右边的某个元素，则与右边的这个元素构成逆序对的个数是 mid-i+1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int s[100005]; 
long long gb_sort(int l,int r){
    int tmp[100005];
    if(l>=r) return 0;
    int mid=l+r>>1;
    //递归左边的数量+递归右边的数量 
    long long res=gb_sort(l,mid)+gb_sort(mid+1,r); 
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(s[i]<=s[j]){
            tmp[k++]=s[i++];
        }
        else{
            res+=mid-i+1; //一个在左，一个在右 ，直接加的，左边下标为i第数的后面的数就不用再跟下标是j的比较了 
            tmp[k++]=s[j++];
        }
    }
    while(i<=mid){
        tmp[k++]=s[i++];
    }
    while(j<=r){
        tmp[k++]=s[j++];
    }
    //物归原主 
    for(i=l,j=0;i<=r;){
        s[i++]=tmp[j++];
    }
    return  res; 
}
int main(int argc, char** argv) {
scanf("%d",&n);
for(int i=0;i<n;i++){
    scanf("%d",&s[i]);
}
long long t=gb_sort(0,n-1);
printf("%lld\n",t);
    return 0;
}