逆序对==最少相邻交换次数（归并排序与树状数组的应用）

1.归并排序求逆序对：

运用归并排序递归函数统计逆序数，简单又实用——O(nlogn)

2.树状数组求逆序对：

先建立 原数组_计数排序后的_树状数组
利用树状数组动态求前缀和的性质:
正向枚举统计前面比自己大的数的个数 或者 反向枚举统计后面比自己小的数的个数（即逆序数）。

注意：下标必须从1开始，防止0=lowbit(0)在ask函数中陷入死循环
缺点：因为用了计数排序，数值的范围不能太大，否则树状数组会太大导致MLE，也可以先用离散化缩小数的范围再用树状数组求逆序对

1. AcWing 107. 超快速排序

• 逆序对：

  第一：求逆序对输出即可
  总共时间复杂度为：O(nlogn)

• 点击查看代码

2. AcWing 1215. 小朋友排队

• 逆序对：

  第一： 求每个数的最少被交换的次数，因为一次相邻交换会有两个数被交换，所以每个数的最少被交换次数之和==2倍最小交换次数==2倍逆序数，所以每个数的最少交换次数==前面比自己大的数的个数+后面比自己小的数的个数
  第二：用树状数组或者归并排序求每个数最少被交换次数然后转换为不高兴度求和输出即可

  注意：用归并排序时，原数组和临时数组要用pair型，在初始时将数值与下标绑定，便于后续计算每个数被交换的次数
  总共时间复杂度为：O(nlogn)

• 点击查看代码

3. AcWing 505. 火柴排队

• 逆序对：

  第一：题意：求最少交换次数（相邻交换）== 求逆序对，且是求相对逆序对：即b数组相对a数组的逆序对
  第一：因为离散化不改变相对逆序对且有利于求缩小范围求逆序对，所以我们先进行离散化
  第一：离散化：排序+去重+归位
  第一：映射：求相对逆序对转换为求其中一个数组的逆序对
  第一：求逆序对：用归并排序或者树状数组求逆序对输出即可
  总共时间复杂度为：O(nlogn)

• 点击查看代码