这题用树状数组比归并排序快很多啊~~~
一个是500多一个2000多。
这题用树状数组,主要有两点
I.离散化,把n个数映射到1-n里面,不然内存不够,
II.求一个数组的某一个数据的前面所有数据中比它小(或大)的所有数的个数
对于第一个,我们可以用一个struct,然后里面存两个信息,一个是val,一个是no,其中val是输入的数,no是用来离散化的。
对于第二个,很多人说是树状数组的基本功了,但是我觉得看怎么结束树状数组的。在这里你可以对每一个数update(a[i],1),然后再getsum(a[i])(a[i]是离散化后的数组)。这样的话,你再用i - getsum(a[i])就是逆序数的对数了,如果不好理解的话,可以用5 2 1 4 3这个数组来模拟下。
对于这两个问题解决了之后,这题就简单了
下面给出代码(还是建议自己先想,不过离散化没接触的,可能会比较难想,树状数组还行吧)

CODE