CSP-S 提高级 · CSP 2026 提高级第一轮 第 14 题

【单选】用归并排序统计逆序对，合并部分的核心代码如下。若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果（ ）。

// 归并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) {
    tmp[k++] = a[i++]; // 取左半段元素
}
else {
    tmp[k++] = a[j++]; // 取右半段元素
    ans += mid - i + 1;
}

归并统计逆序对时，a[i] <= a[j] 表示"左边元素不大于右边，不算逆序"；改成严格小于后，相等的元素对也被计入，于是答案变成满足 i < j 且 a[i] ≥ a[j] 的数对个数（即"逆序对 + 相等对"）。

认为改成 < 后只是"更严格所以更少"（刚好相反，条件变苛刻后统一归入 j 分支，统计值只会不减）；或者误以为结果翻倍。

解析

本题考查归并排序统计逆序对时比较符号的影响。

// 合并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) tmp[k++] = a[i++];   // 取左半段元素
else {
    tmp[k++] = a[j++];                 // 取右半段元素
    ans += mid - i + 1;                // 一次性计入"左半剩余元素"个数
}

原写法 a[i] <= a[j] 的含义

当取右半段的 a[j] 时，说明 a[:i] 中所有剩余元素都 > a[j]，它们各自与 a[j] 构成一个逆序对（i < j 且 a[i] > a[j]），因此一次加 mid − i + 1 个。此时统计的是严格逆序对：i < j 且 a[i] > a[j]。

改成 a[i] < a[j] 后

• 若 a[i] < a[j]：仍取左半段，计入正常；
• 若 a[i] == a[j]：现在落入 else 分支，取右半段元素并 ans += mid − i + 1 —— 于是相等元素对被算成了"逆序"。

所以 ans 统计的集合从 {i<j 且 a[i] > a[j]} 变成 {i<j 且 a[i] ≥ a[j]}，即 原来的逆序对 + 所有相等的数对。

答案 C（变为满足 i < j 且 a[i] >= a[j] 的数对个数）。

其他选项为什么错

• A. 完全不变：相等的元素对会带来增量，只有数组元素全部互不相同时才恰好不变；
• B. 变为原来的两倍：增量取决于相等元素的多少，没有"翻倍"这种定量关系；
• D. 变为原来的一半：条件变"苛刻"只会让进入 else 分支的次数变多，ans 不可能减少，更不会减半。

举例验证

数组 [2, 2]：

• 原写法：merge 时 a[0] <= a[1] → 取左边，ans = 0（无逆序对）✓
• 改写法：a[0] < a[1] 为假 → 取右边，ans += 1 → ans = 1 = "满足 i<j 且 a[i] ≥ a[j] 的数对" ✓

记忆点

• 统计严格逆序对用 <=，统计"非逆序"（≥ 的数对）用 < —— 符号方向极易记反，判断时抓一句："等号跟着哪个分支，那个分支就不计数"；
• 归并排序统计逆序对的复杂度 O(n log n)，优于树状数组 O(n log n) 的常数表现也不错；
• 与"相等元素算不算逆序"相关的还有排序稳定性问题：<= 保证稳定，< 会破坏稳定性。