逆序对

1.求法

法一

归并排序。 归并排序用到了二分的思想，在排序过程中如果a[ i ]<=a[ j ]就不会产生逆序对，如果a[ i ]>a[ j ]就会产生mid-i+1个逆序对，因为做归排的时候l～mid和mid+1～r都是已经排好序的所以如果a[ i ]>a[ j ]那么a[ i+1 ]~a[ mid ]也就都大于a[ j ] ## 法二 树状数组。 首先我们只关心两个数之间的大小关系，其具体数值并不重要，所以为了方便处理，我们将输入的n个数进行离散化，即按照大小关系把a[1]到a[n]映射到1到num之间的数，为了保证原有的大小关系，其中num为不同的数字的个数。 这样本题的描述方式可以换为：对于a[i]求a[i]后面有多少个数比它小？于是我们可以用树状数组来解决：我们从第n个数开始倒序处理，用树状数组的方法维护一个cnt数组，其query(x)前缀和表示到当前处理的第i个数为止,映射后值在1到x之间的数一共有几个。如果a[i]映射后的值为y，那么比a[i]小的个数就等于query(y-1)对于维护，只需要在该次查询结束后再y这个位置执行树状数组的修改操作即可。 整个算法的复杂度为 nlongn

2.应用

1.逆序对个数=这个数后面比它小的数个数。 2.逆序对个数=这个数邻项交换到顺序位置时的操作次数。 3.可用于求平均值不小于M的子段个数（前缀和顺序对）。