int数组的最优反演计数

Question

今天我正在寻找当地信息学奥林匹克运动会的最新考试,我发现了一个有趣的问题.简而言之,它要求给定一个整数数组,计算它有多少个反转,其中反转是一对指标i,j例如i > j和A[i] < A[j].非正式地,反转的数量是无序的对的数量.最初我做了一个O(n²)解决方案(是的,天真的),但看到它不适合输入的大小,我想到了更多的问题,然后我意识到可以O(n log n)通过一个变体在一段时间内做到这一点合并排序,处理好输入的大小.

但是看到输入约束(n整数之间1 and M,没有重复),我想知道我的解决方案是否是最优的,或者你知道是否有任何其他解决方案来解决O(n log n)运行时问题？

Answer 1

由于Chan和Patrascu,文献中的最佳结果是O(n√(log n))算法.不知道常数.