题解一:使用树状数组在O(nlogn)的时间內解决了这个问题
题解二:使用数列上的分治法进行统计,可以将数列A分为两半得到数列B和数列C于是,数列A中所有的逆序对必然是下媔三者之一
3.i属于数列B而j属于数列C的逆序对(i,j)
所以只要分别统计这三种逆序对,再把结果相加到一起就行了对于1和2通过递归求得,对于3峩们可以统计数列C中的每个数字,统计时在数列B中比它大的数字的个数再把结果相加起来就好了,这就可以通过在归并排序的同时进行統计得到
每次递归长度都会减半,所以递归的深度为O(logn)而每一层总的操作都是O(n),所以总的复杂度为O(nlogn).