NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 17 题

对于序列 $7,5,1,9,3,6,8,4$，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少 $3$。

这道题考的是逆序对计数与元素贡献。拿到题先别急着删，心里默数：把要删的那个数从序列里‘拿掉’，它原本参与的所有逆序对（它比后面大的，或前面比它大的）都会消失，数清楚这个贡献值是不是 3 就行。

很多学生会把‘逆序对总数’和‘某个数参与的逆序对’搞混，或者数数时漏掉一边（比如只数它后面比它小的，忘了前面比它大的）。还有一种常见错误是看到 5 和 3 都减了 3 个，就以为 C 和 B 都对，其实 5 参与的是 4 个逆序对，题目只问减少 3 个的，所以 B 是坑。

考点与概念 本题核心是理解逆序对：序列中前面位置 i 与后面位置 j（i<j）且 a[i]>a[j] 的一对。删除一个元素，所有包含该元素的逆序对都会消失，消失的数量就是该元素‘贡献’的逆序对数。题目要求找到贡献恰好为 3 的元素。

命题视角 命题人喜欢考这种‘局部贡献’而非全局统计，因为直接数总数容易眼花，但数单个元素的贡献只要按规则扫一遍就能搞定。坑点往往在边界：比如 5 和 3 的贡献都是 3，但 5 实际参与 4 个，学生容易凭直觉选错。

思考路径 拿到序列 7,5,1,9,3,6,8,4，逐个假设删除，数贡献：

• 删 7：后面比 7 小的有 5,1,3,6,4，共 5 个，贡献 5 → 排除。
• 删 5：前面比 5 大的有 7（1 个），后面比 5 小的有 1,3,4（3 个），共 4 个，贡献 4 → 排除。
• 删 1：前面比 1 大的有 7,5,9,3,6,8,4（7 个），后面没有比 1 小的，贡献 7 → 排除。
• 删 9：前面比 9 大的无，后面比 9 小的有 3,6,8,4（4 个），贡献 4 → 排除。
• 删 3：前面比 3 大的有 7,5,9（3 个），后面比 3 小的无，贡献 3 → 符合。
• 删 6：前面比 6 大的有 7,9（2 个），后面比 6 小的有 4（1 个），共 3 个，贡献 3 → 符合。
• 删 8：前面比 8 大的有 9（1 个），后面比 8 小的有 4（1 个），共 2 个，贡献 2 → 排除。
• 删 4：前面比 4 大的有 7,5,9,3,6,8（6 个），后面无，贡献 6 → 排除。

避坑提醒 最容易栽跟头的就是 5，因为它和 3 一样都‘看着像’减了 3 个，但 5 多了一个 (7,5)，实际贡献是 4。还有学生数数时只数后面，忘了前面比它大的也算贡献，比如 3 前面有 7,5,9 三个，必须全算上。

考频与趋势 逆序对相关题目在题库中已出现 249 次，跨度从 2008 到 2026，逐年分布为：2008 年 2 题、2009 年 3 题、2010 年 3 题、2011 年 1 题、2012 年 2 题、2013 年 1 题、2014 年 2 题、2015 年 1 题、2017 年 2 题、2018 年 1 题、2019 年 1 题、2020 年 2 题、2021 年 3 题、2022 年 5 题、2023 年 22 题、2024 年 51 题、2025 年 57 题、2026 年 50 题、null 年 40 题。按赛事分：GESP 五级 74 题、CSP 入门级 44 题、GESP 四级 39 题、GESP 八级 27 题、GESP 七级 26 题、GESP 六级 12 题、NOIP 提高组 初赛 12 题、CSP 提高级 9 题、NOIP 普及组 初赛 6 题。从 2023 年突然爆发（22 题）到 2025-2026 年持续高位（57、50 题），说明逆序对及其变体已成为近年高频考点，命题人明显在加大对该知识点的考察力度。

未来预测 基于上述数据，未来 1-2 年逆序对相关题目仍会保持高频率出现，形式可能更灵活：比如给出部分逆序对信息反推原序列，或在动态插入/删除场景下实时计算贡献。暂无足够依据预测具体年份的题量，但可以肯定的是，掌握‘元素贡献’这一核心思想是应对此类题目的关键。