题目：给你一个n，再给你n个乱序的数，问你有多少对逆序对。（一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序）比如 1 5 3 2 7 这个序列中就有3个逆序对（5，3）（5，2）（3，2）
思路：分治，利用归并排序找出逆序对
归并排序的原理就是将序列拆成一对数一对数进行合并排序
之后再将合并后的数字再进行合并排序
最终形成有序数列
而合并的过程中则是利用指针将两个序列中的数进行比较，如果第一个序列的数大就将第二个序列的数插入，并且第二个指针后移，反之则不插入，将第一个指针后移看该数是否大于第二个序列的数，重复流程并储存于一个中间数组即可完成排序
比如：1、5序列与3合并，当1<3时将3放于5的前面
而这里的逆序对则是跟归并排序的思路类似，因为归并排序把第二个数向前移到第一个序列的过程不就是找逆序对的过程吗
那这里经过了多少距离该如何去算呢？
再举例 1 5 3，这时中间位置mid=1，左指针p1=0，右指针p2=2。
因为1<3所以p1++；
而到了p1=1的时候3插入了5前面
而3移到5前面的过程不就是mid-p1+1吗
（mid-p1+1就是移动的距离，该处+1的原因是因为p1这时候指向的是大于p2的数，你要把p1这个时候所指的数加上去
代码：

#include <iostream>

using namespace std;
int a[1000000];
int b[1000000];//b[i]作为中间存储变量保存正确的排序
long long ans=0;
void merge_(int l,int mid,int r){//合并操作
       int p1=l,p2=mid+1;
       for(int i=l;i<=r;i++){//从左边到右边的数全部扫一遍重新排序
        if(p1<=mid &&((p2>r)||(a[p2]>a[p1]))){//条件一防止p1越过中线，条件二是当p2达到右边界或者目前右边的数小于左边的数时就把左边的数放在前面并且记下来
            b[i]=a[p1];
            p1++;
        }else{
            b[i]=a[p2];
            p2++;
            ans+=mid-p1+1;//因为这时候p1已经指的是下一个数了，所以要加一，把p1指的那个数加回来
        }
       }
       for(int i=l;i<=r;i++){
        a[i]=b[i];
       }
}
void divide(int l,int r){//“分”的策略先利用递归将数组全部数变成一个一个数进行拼凑
    int mid=(l+r)/2;
    if(l<r){
    divide(l,mid);
    divide(mid+1,r);
    }
    merge_(l,mid,r);
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    divide(0,n-1);
    cout<<ans;

    return 0;
}
/*
5
1 5 3 6 7
*/