求助：不使用归并排序的O(nlogn)逆序数计算算法（C++）实现

兄弟，我太懂这种卡壳的感觉了——盯着指定的伪代码一步步走，结果不小心搞出嵌套循环，复杂度直接从目标的O(nlogn)飙到O(n²logn)，明明知道归并排序能搞定，但偏得守着给定步骤来，那种憋屈感简直拉满。

既然你说要优化第二步，那大概率你的伪代码是分治框架（毕竟这是逆序数计算常见的指定步骤方向），当前踩坑的点肯定是在「统计跨左右子数组的逆序对」这一步用了嵌套循环逐个比对。那直接给你解决思路：利用递归后左右子数组已排序的特性，用双指针法替代嵌套循环，把这一步的时间复杂度从O(n²)压到O(n)，整体复杂度自然就达标了。

具体优化方案（完全贴合分治类伪代码步骤） #

假设你的伪代码步骤是这类标准分治结构（对应你要优化的第二步）：

• 若数组长度≤1，返回0（无逆序数）
• 将数组拆分为左半部分L、右半部分R
• 递归计算L的逆序数count_L、R的逆序数count_R
• [你要优化的第二步] 统计L中元素大于R中元素的跨逆序对数量count_cross
• 合并L和R为有序数组（为后续递归的跨逆序统计做准备）
• 返回count_L + count_R + count_cross

你之前的第二步可能是这么写的（伪代码示例）：

count_cross = 0
for each element in L:
    for each element in R:
        if L_element > R_element:
            count_cross +=1

这种嵌套循环直接把第二步拉到O(n²)，叠加分治的logn后就成了O(n²logn)。

替换成双指针法的优化版第二步

因为递归处理后，L和R已经是有序数组（升序为例），我们可以用双指针一次遍历完成统计：

• 初始化两个指针i（指向L的起始）、j（指向R的起始），count_cross = 0
• 遍历过程中：
  • 如果L[i] > R[j]：说明L中从i到末尾的所有元素都大于R[j]（因为L是升序），直接批量加上len(L) - i到count_cross，然后j右移
  • 否则：i右移，继续比对下一个L元素
• 直到i或j遍历完对应子数组

给你个Python代码示例（完全对应优化后的第二步）：

def count_cross_pairs(L, R):
    i = j = 0
    cross_count = 0
    len_L = len(L)
    while i < len_L and j < len(R):
        if L[i] > R[j]:
            # 批量统计：L[i...]都比R[j]大
            cross_count += len_L - i
            j += 1
        else:
            i += 1
    return cross_count

为什么这能行？ #

核心就是利用了左右子数组有序这个递归带来的“隐藏福利”——不用再逐个比对每个L元素和每个R元素，而是通过双指针的移动，批量统计符合条件的逆序对，直接干掉了嵌套循环，把第二步的时间复杂度从O(n²)降到O(n)。加上分治的logn层级，整体时间复杂度就完美达到O(nlogn)了，而且完全没有偏离你必须遵循的伪代码步骤，只是把低效的嵌套循环换成了更聪明的遍历方式。

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