（坚持每天都写算法）算法基础复习part1基础算法1-3

//逆序列，因为是可以看成不同的子数组在比较（排列组合），所以可以考虑分数组的方法
//如果只是分数组，很容易想到分治，而运用了分治的数组算法有排序，恰好又是逆序列，所以可以考虑
//分治有两种，快排和归并，快排是先交换后再划分，会来不及计算res（直觉）就打乱原本的数组，不行
//归并是先一步步划分然后再替换顺序，而且有替代数组，可以在排序的过程中就算出来,并且排完序了
//其实归并的目的是排序，关键是归并使用的算法是 递归和分治，因为这道题的关键和归并的重点一样，所以我们
//可以在归并的基础上修改

//更新，按照自己后来的想法，改成“很容易想到最优子结构，划分成一个个小数组，排序的划分小数组的可以考虑快排和归并“

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];
int temp[N];

long long find(int a[] , int l , int r){
    if( l >= r) return 0;
    int mid = (l + r) >> 1;
    long long res = 0;
    res += find(a , l , mid);
    res += find(a , mid + 1 , r);
    
    int i = l , j = mid + 1;
    int k = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) temp[k ++] = a[i ++];//正常顺序，故不记录
        else{
            temp[k ++] = a[j ++];
            res += mid - i + 1;//当只有两个数的时候，mid为i，两个数逆序列只有一个,得出可能成立的公式，进行验证，结合下面的排序，直接相加即可。
        }
    }
    while(i <= mid ) temp[k ++] = a[i ++];
    while(j <= r) temp[k ++] = a[j ++]; 
    
    for(i = l , j= 0 ; i <= r ; i ++ , j ++) a[i] = temp[j];
    //关于要不要重新排序（毕竟目的不是排序，res会在这一步先加到，那么这一步有没有必要存在就是个问题了
    //b区间的排序，不会影响到总体的res数量，因为对于某个元素来讲（按顺序从左往右），b区间排序就排序，又不能
    //排到该元素的前面（or后面，看你选择了哪两个区间），区间又不一样。
    //重新排序能够减短时间，
    //比如序列是这样的
    // 4 5 6 | 1 2 3
    // 当你发现 4 比 3 大的时候，也就是说右边最大的元素都小于左边最小的元素，
    // 那么左边剩下的5和6都必然比右边的所有元素大，因此就可以不用数5和6的情形了，直接分别加上右半边的元素个数就可以了
    //具体看该链接：https://www.acwing.com/solution/content/5508/
    
    //更新，以上的思路建议先看懂整体的思路再看。
    return res;
    
    
}
int main(){
    int n;
    cin >>n;
    for(int i = 0 ; i < n; i ++){
        cin >> a[i];
    }
    
    cout <<find (a , 0 , n - 1);
}