逆序数的几种求法

什么叫逆序数

对于某一个数来说，它的逆序数等于在它之前有多少个比它大的数

对于某一个序列来说，逆序数等于所有数的逆序数之和

例如

 序列      5   1    5   2

逆序数   0   1    0   2

序列的逆序数 1+2=3

来看逆序数的求法

首先将定义一个结构体，存数列的值和下标，然后按数值从大到小（数值相同按下标从大到小）sort一下

然后建立树状数组，从最大的元素开始，将其标记，即   add（p【i】.id，1）

利用其query（i）查询当前1----i的和

对于第i大的数，由于之前所有比它大的数已经标记，所以query（i）就是当前数的逆序数

例如  5  6  3  8  2     其排序之后即是      2   3   5   6   8   将求对应的值的逆序数的问题转化成了求下标对应的逆序数按求逆

         1  2  3  4  5                                    5   3   1   2    4

序数的方法，先求下标的逆序数  即：   0 + 1 + 2 + 2 + 1  =   6 ，答案即是序列的逆序数，

换一种思路来看，  为了避免加入顺序而导致逆序数的不正确，所以从后面开始逆序，因为已经转化成下标的逆序

所以只需看下标即可，  5   3   1   2   4  对于4的逆序只有5，在c[5]+1，

                                                              对于2的逆序有5,3，在c[5]+1,c[3]+1

                                                              其余类似。。。。。

然后对于3来说的树状数组求1~3的和，即是求以3为逆序数（此例是1,2）的数的个数，

同理对于 i 来求1~i 之间的和，就是来求以 i 为逆序数的数的个数，最后求个总和，也就是所要求的该数列的逆序数。

代码：