如何统计数组中符合条件的大逆序对数量且时间复杂度为O(nlogn)

核心思路1：离线处理+树状数组（时间复杂度严格O(nlogn)，实现更简单） #

这个思路完全避开归并排序丢失索引的问题，从大逆序对的约束出发反向遍历：

• 大逆序对要求 2*i < j 且 A[i] > 2*A[j]，我们可以从右往左遍历j，每次计算以当前j为右端点的合法大逆序对数量，累加得到总结果
• 维护一个指针p，初始为0，每次处理j前，先把所有索引小于等于(j-1)//2的A[i]插入树状数组：因为这些i天然满足2*i < j的索引约束，不需要再额外判断
• 插入完成后，查询树状数组中数值大于2*A[j]的元素个数，加到总答案里即可

注意：如果A的数值范围很大，需要提前做离散化处理：把所有A[i]和2*A[i]放到同一个数组里排序去重，映射为1~2n的整数，就能直接用树状数组查询。

核心思路2：归并排序改进版（保留索引信息） #

如果你想沿用归并排序类的逆序对统计思路，只需要给每个元素绑定原索引即可：

• 分治过程中每个元素存为(原索引i, 数值A[i])的二元组，递归处理左右两个子区间，返回两个结果：当前区间的大逆序对总数、当前区间按数值升序排序后的二元组列表
• 统计跨左右区间的合法对时，用双指针遍历：
  1. 左右两个列表已经按数值升序排好，初始化右指针p=0
  2. 遍历左半区的每个元素(i, val_i)，移动右指针p，把所有右半区满足val_i > 2*val_j的元素的j存入一个临时有序数组（因为右半区按数值升序，p只会单向移动）
  3. 用二分查找在临时有序数组中找到大于2*i的j的数量，加到当前层的统计结果里
• 最后把左右两个有序列表合并，返回给上层即可

这个思路如果用二分统计索引，时间复杂度是O(n(logn)^2)，如果提前把右半区的索引也按数值排序的顺序预处理前缀有序数组，可以优化到严格O(nlogn)，但实现复杂度比离线树状数组方案高。

内容的提问来源于stack exchange，提问作者noob