#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
int main(){ 

    //day:5/29
    //question:逆序数问题
    //input: 9 2 7 4 -1 
    //output:(9,2),(9,7),(9,4),(9,-1),(2,-1),(7,4),(7,-1),(4,-1)

    //方法一：暴力枚举法
    vector<int> v={ 9,2,7,4,-1};
    int ans=0;
    for(int i=0;i<v.size();i++){ 
        for(int j=i+1;j<v.size();j++){ 
            if(v[i]>v[j]){ 
                ans++;
                cout<<"("<<v[i]<<","<<v[j]<<")"<<endl;
            }
        }
    }
    cout<<ans;
    system("pause");
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

int crossSearch(int l, int m, int r, vector<int> &v)
{ 
    vector<int> v1 = v;
    int i = l;
    int j = m + 1;
    int k = 0;
    int s3 = 0;
    while (i <= m && j <= r)
    { 
        if (v1[i] > v1[j])
        { 
            v[l + k] = v1[j];
            s3 += m - i + 1; //找到v1[j]在v1中的位置，计算m到i位置的个数
            k++;
            j++;
        }
        else
        { 
            v[l + k] = v1[i];
            k++;
            i++;
        }
    }
    if (i <= m)
    {  //当右边遍历完，把左边依次添加到左边,此处要注意！赋值给的一定是l+k,因为不加l，则对左数组无影响，对右数组有影响，因为k是相对的
        while (l+k <= r && i <= m)
        { 
            v[l+k] = v1[i];
            k++;
            i++;
        }
    }
    else
    {  //当左边遍历完，把右边依次添加到左边
        while (j <= r && k <= r)
        { 
            v[l+k] = v1[j];
            k++;
            j++;
        }
    }
    return s3;
}
int partition(int l, int r, vector<int> &v)
{    
    if (l >= r)
    {        
        return 0;
    }
    int m = (l + r) / 2;
    int s1= partition(l, m, v);     //左边的逆序对数
    int s2 = partition(m + 1, r, v); //右边的逆序对数
    int s3 = crossSearch(l, m, r, v);  //中间的逆序对数
    int ans = s1+s2+s3;

    return ans;
}

int main()
{ 
    //方法二：分治法+归并排序9 2 7 4 -1
    vector<int> v = { 9, 2, 7, 4, -1};
    int r=partition(0,v.size()-1,v);
    cout<<r;
    system("pause");
    return 0;
}