网上问“小鱼比可爱 Java 版”的人真的不少尤其和蓝桥杯、Java 排序这些关键词放在一起搜出来的讨论热度比想象中高。我一开始以为是个什么高深算法结果一看样例就明白了这是一道典型的“数组排序 索引映射”练手题很多同学暴力循环写完就交数据一大的时候直接超时。真正把它吃透之后你会发现它把对象排序、稳定排序、逆序对计数这些 Java 基础考点全串起来了甚至拿来当 Java 面试的算法题都够格。这篇就按我自己的刷题视角来写先讲清楚题干的坑再给出暴力写法然后重点讲解归并排序的优化思路最后分享一些实际提交时踩过的 Java 细节。无论你是备战蓝桥杯还是想弄懂“左侧小于当前数”这类计数题这篇都能直接用上。1. 题目到底在问什么不是全局比较是每个位置的左侧计数题目描述一般是这样的N 条小鱼排成一队编号从 0 到 N-1每条鱼有一个可爱值 a[i]整数可以为负。现在每条鱼都想知道自己左边有多少条鱼比自己“不可爱”也就是可爱值严格小于自己。输出一行 N 个整数第 i 个数代表第 i 条鱼左侧小于 a[i] 的元素个数。拿最常见的样例来说输入 6 4 3 0 5 1 2 输出 0 0 0 3 1 2手动验证一下第 0 条鱼可爱值 4左边没有鱼所以是 0。第 1 条鱼可爱值 3左边只有 4。4 不小于 3所以是 0。第 2 条鱼可爱值 0左边 4 和 3 都比 0 大所以是 0。第 3 条鱼可爱值 5左边 4、3、0 都比 5 小正好 3 个。第 4 条鱼可爱值 1左边只有 0 比 1 小所以是 1。第 5 条鱼可爱值 2左边 0 和 1 都比 2 小所以是 2。这个理解非常关键因为它意味着你不是求整组数据的逆序对总数而是要把每个位置算出来的结果单独存下来。如果题目改成“右边比自己大的数量”“全局逆序对数量”代码改动都不大但思路会差一点后面我会在扩展部分说。三个容易忽略的点也是这类题的通用陷阱严格小于。a[j] a[i] 才计数相等不算。如果你写 样例可能没问题但遇上大量重复可爱值直接错。只统计左侧。不能把自己算进去也不能统计右边。可爱值可能是负数。这就意味着不能直接开一个“值域大小”的数组去计数如果要用树状数组必须离散化而归并排序天然不需要管值域。2. 暴力写法能过样例但大数据必挂先给一段最直白的 Java 实现很多初学者第一反应就是它import java.util.Scanner; public class FishCompareBrute { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { int cnt 0; for (int j 0; j i; j) { if (a[j] a[i]) { cnt; } } if (i 0) { sb.append( ); } sb.append(cnt); } System.out.println(sb); } }逻辑没毛病复杂度也很明确两层循环总比较次数是 0 1 2 ... (N-1)也就是 N*(N-1)/2。N1000约 50 万次比较瞬间出结果。N5000约 1250 万次比较Java 大概几百毫秒到 1 秒能接受。N50000约 12.5 亿次比较必超时。N100000约 50 亿次比较想都别想。在蓝桥杯这类竞赛场景里N 一旦到 10^5暴力就是“样例过、评测超时”的典型死法。所以暴力代码的正确用途是小数据验证、写对拍程序、给优化版本做正确性对照。别指望它拿满分。3. 归并排序解法把“左侧小于”变成归并时的计数核心思路其实一句话归并排序在合并两个有序区间时左半区间的所有元素在原数组里都排在右半区间前面。所以当右半区间的某个元素被放进临时数组时左半区间里已经弹出去的元素就是它左边比它小的元素。这句话听起来有点绕我拆开解释。假设当前正在合并区间 [l, mid] 和 [mid1, r]。这两个子区间已经被分别排好序了而且左半区间的下标全部小于右半区间的下标。归并的标准写法是两个指针 i、j 分别指向左右两个区间的头部谁小谁先进临时数组。我们稍微改一下规则当 a[i] a[j] 时说明左半当前元素比右半当前元素小把左半元素放进临时数组i。当 a[i] a[j] 时说明右半当前元素比左半当前元素小或相等。这时把右半元素放进临时数组同时把答案累加ans[原下标] (i - l)。为什么是 i - l因为左半区间从 l 到 i-1 的元素都已经弹出它们全部严格小于当前这个右半元素。我们不需要逐个去判断数量直接就是 i-l。这里必须强调“严格小于”因为弹出左半的条件是 a[i] a[j]等于的情况下左半不会被弹出。完整代码我贴出来这个版本是直接可提交的import java.util.Scanner; public class FishCompareMerge { static int[] a; static int[] pos; static long[] ans; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); a new int[n]; pos new int[n]; ans new long[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); pos[i] i; } mergeSort(0, n - 1); StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { if (i 0) { sb.append( ); } sb.append(ans[i]); } System.out.println(sb); } static void mergeSort(int l, int r) { if (l r) { return; } int mid (l r) 1; mergeSort(l, mid); mergeSort(mid 1, r); merge(l, mid, r); } static void merge(int l, int mid, int r) { int[] tmpA new int[r - l 1]; int[] tmpPos new int[r - l 1]; int i l; int j mid 1; int k 0; while (i mid j r) { if (a[i] a[j]) { tmpA[k] a[i]; tmpPos[k] pos[i]; i; } else { ans[pos[j]] i - l; tmpA[k] a[j]; tmpPos[k] pos[j]; j; } k; } while (i mid) { tmpA[k] a[i]; tmpPos[k] pos[i]; i; k; } while (j r) { ans[pos[j]] i - l; tmpA[k] a[j]; tmpPos[k] pos[j]; j; k; } System.arraycopy(tmpA, 0, a, l, k); System.arraycopy(tmpPos, 0, pos, l, k); } }注意代码里维护了一个 pos 数组记录每个可爱值对应的原数组下标。因为排序过程中 a 数组会不断变化如果没有 pos最后你根本不知道 ans 里的数字应该输出在哪个位置。4. 用手推一遍样例每个数字的答案是怎么累加的这一步我建议你亲手走一遍比看十遍代码都有用。我用样例 4 3 0 5 1 2 来演示只挑几个关键的合并过程。先看最底层的两个相邻元素的合并。合并区间 [4,5] 时左半是索引 4 的 1右半是索引 5 的 2。1 2所以左半先弹出然后右半 2 弹出时i-l 1于是 ans[5] 加上 1。这一步对应的事实是索引 5 的鱼左边只有一个索引 4 的鱼的可爱值 1 比 2 小。再看合并区间 [2,3]左半是 0右半是 5。0 5左半弹出右半 5 弹出时ans[3] 加上 1。这一步对应的事实是索引 3 的鱼在区间 [2,3] 这个范围内左侧只有索引 2 的 0 比 5 小。然后合并更大的区间 [0,3]。此时左半已经排成 3 4原索引 1,0右半已经排成 0 5原索引 2,3。归并过程3 和 0 比3 0 不成立右半 0 弹出ans[2] 0因为左半还没弹出任何元素。3 和 5 比3 5 成立左半 3 弹出。4 和 5 比4 5 成立左半 4 弹出。左半耗尽右半 5 弹出ans[3] 2。于是 ans[3] 之前有 1现在再加 2最终变成 3。这就对上了样例输出。这里有个很关键的理解每个元素并不是在一步之内找到所有左侧小于它的元素而是在不同层级的合并过程中分别把不同区间的贡献累加起来。归并排序天然把整个数组拆成了一棵分治树每个左侧的“远端元素”都会在某个合并层和当前元素相遇一次。如果你只统计全局逆序对总数代码会更简单只需要一个全局计数器不需要 ans 数组按位置累加。但本题要求每个位置的答案所以必须用 ans[pos[j]] 这种方式逐层累加。这也是很多初学者把逆序对模板背得很熟、却在这题上卡住的原因。5. 几个真实的坑从计数溢出到 IO 超时这类题提交时Java 选手最常见的坑有下面几个我基本全踩过。第一个坑ans 用 int 必炸。最坏情况是数组严格递减比如 5 4 3 2 1 0。此时每条鱼左侧都找不到比自己小的总答案不是很大不对严格递减时左侧小于自己的数量全是 0。真正会很大的是数组严格递增比如 0 1 2 3 4 5第 i 条鱼左侧有 i 条比自己小的总答案是 N*(N-1)/2。N100000 时大约是 49.995 亿明显超过 int 上限 21 亿。所以 ans 必须用 long。这是很多人用 int 交上去 WA 的典型原因。第二个坑等于的情况处理。归并时条件必须是 a[i] a[j] 而不是 a[i] a[j]。如果用 那么相等的左半元素会先弹出。等右半元素弹出时i 已经多走了一步相等的元素就会被错误计入答案。拿数组 1 1 来说正确输出应该是 0 0但如果写 第二个 1 会统计到第一个 1输出变成 0 1。这种 bug 在样例不包含重复值时很难发现所以自己测数据时务必加上全相等的用例。第三个坑pos 数组同步维护。归并时如果你只对 a 排序不动 pos那么 ans[pos[j]] 里的 pos[j] 就不再是原数组下标。我建议把 pos 和 a 一起放进临时数组一起覆盖写回。用两个 int 数组比建一个对象数组更省内存在小数据量下差距不明显但 N10^5 时能差出几 MB而且 Java 对象数组的访问开销更高。第四个坑Scanner 在大数据下的性能。如果 N10^5输入本身不算特别大Scanner 勉强能过但竞赛环境里我建议你还是用 BufferedReader 或一个简单的 FastScanner。输出也一样不要 println 一行一个用 StringBuilder 拼好了一次性输出。这个优化几乎是免费的但很多同学忘了。第五个坑临时数组的创建位置。上面代码在每次 merge 都 new 一个新数组N 大时会有大量小对象创建。更稳的写法是在类里开两个全局数组 tmpA、tmpPos长度等于 Nmerge 的时候直接用对应区间。这样不仅快还能避免频繁 GC 带来的抖动。蓝桥杯这种限时环境GC 抖动有时候就是那个“差一点超时”的元凶。再给一个简单自测用例代码写完先用它验证输入 5 1 1 1 1 1 输出 0 0 0 0 0如果输出不是全 0说明等于处理有问题。另一个用例输入 5 5 4 3 2 1 输出 0 0 0 0 0严格递减时每个位置左边都没有比自己小的所以输出全 0。这个用例能帮你判断“逆序对求错方向”的问题。6. 从这道题延伸出去左侧小于、右侧大于、逆序对都是一套逻辑小鱼比可爱本质上是一道一维偏序计数题。什么叫一维偏序就是你有一个序列要统计每个位置之前满足某个大小关系的元素个数。这类题在算法里可以归为三类左侧小于当前数本题。左侧大于当前数反着比或者用左侧总数减去左侧小于等于当前数。全局逆序对数量所有 i j 且 a[i] a[j] 的对数。这三类都能用归并排序做也能用树状数组做。归并排序版本的优点是不需要离散化直接处理原始数值哪怕可爱值有负数、有 10 位数也没关系。树状数组版本优点是代码思路更统一但需要先把数值离散化成排名等于多一步。如果面试官让你现场写我会优先推荐归并排序原因有三个不会因为离散化错误导致越界访问。代码里天然带着稳定性原理讲起来很顺。可以顺手把“如何求全局逆序对”也答出来显得你对分治理解更深。树状数组版本适合这么用题目已经给了值域范围比如可爱值在 0 到 100000 之间不用离散化。此时 BIT 代码很短查询和更新分别是 O(log n)总复杂度一样。还有一种常见变形是“右侧小于当前数”LeetCode 上有一道很经典的题就是这个。方法可以倒过来做从右往左遍历用树状数组维护已经见过的值也可以用归并排序在合并时统计左半元素有多少个大于右半元素。思路和本题基本一致只是方向改了。如果你能把“小鱼比可爱”彻底理解那道题基本就是白送。7. 我的实际体会别急着背模板先搞懂“计数发生在哪一步”这道题我前前后后写过三版。第一版是暴力纯为了对拍。第二版我直接背了逆序对的归并模板结果输出全乱因为模板只统计总数不关心每个位置各自的答案。后来我把归并过程一行行打印出来才真正看明白每个元素和左侧不同区间的比较是分散在多次合并里的必须把答案逐层累加到对应原下标上。从那以后我再遇到“统计每个位置满足某种关系的数量”这类题第一反应就不是套模板而是先想清楚这个关系会在哪个分治步骤里被恰当地观察到。一个小技巧分享给你debug 的时候别打印整个数组在 merge 方法里打一行关键信息就行比如当前 l、mid、r以及每次给 ans[pos[j]] 增加的量。配合小数据马上就能看出计数逻辑哪里不对。最后再说说提交策略。如果题目没有给数据范围或者你拿不准我会把归并版本当成默认答案暴力版本只用来对拍。归并写起来多花两分钟但换来的是从 N5000 到 N100000 都能稳过的安心感。蓝桥杯这种比赛能 AC 和不能 AC 往往就差在“有没有提前想到复杂度”上。小鱼比可爱这道题就是这个道理最好的练习。 
长河君 · 2026/10/10 14:49:58 · 阅读 1.2k 小鱼比可爱 Java 版：归并排序如何高效统计左侧小于当前数
网上问“小鱼比可爱 Java 版”的人真的不少尤其和蓝桥杯、Java 排序这些关键词放在一起搜出来的讨论热度比想象中高。我一开始以为是个什么高深算法结果一看样例就明白了这是一道典型的“数组排序 索引映射”练手题很多同学暴力循环写完就交数据一大的时候直接超时。真正把它吃透之后你会发现它把对象排序、稳定排序、逆序对计数这些 Java 基础考点全串起来了甚至拿来当 Java 面试的算法题都够格。这篇就按我自己的刷题视角来写先讲清楚题干的坑再给出暴力写法然后重点讲解归并排序的优化思路最后分享一些实际提交时踩过的 Java 细节。无论你是备战蓝桥杯还是想弄懂“左侧小于当前数”这类计数题这篇都能直接用上。1. 题目到底在问什么不是全局比较是每个位置的左侧计数题目描述一般是这样的N 条小鱼排成一队编号从 0 到 N-1每条鱼有一个可爱值 a[i]整数可以为负。现在每条鱼都想知道自己左边有多少条鱼比自己“不可爱”也就是可爱值严格小于自己。输出一行 N 个整数第 i 个数代表第 i 条鱼左侧小于 a[i] 的元素个数。拿最常见的样例来说输入 6 4 3 0 5 1 2 输出 0 0 0 3 1 2手动验证一下第 0 条鱼可爱值 4左边没有鱼所以是 0。第 1 条鱼可爱值 3左边只有 4。4 不小于 3所以是 0。第 2 条鱼可爱值 0左边 4 和 3 都比 0 大所以是 0。第 3 条鱼可爱值 5左边 4、3、0 都比 5 小正好 3 个。第 4 条鱼可爱值 1左边只有 0 比 1 小所以是 1。第 5 条鱼可爱值 2左边 0 和 1 都比 2 小所以是 2。这个理解非常关键因为它意味着你不是求整组数据的逆序对总数而是要把每个位置算出来的结果单独存下来。如果题目改成“右边比自己大的数量”“全局逆序对数量”代码改动都不大但思路会差一点后面我会在扩展部分说。三个容易忽略的点也是这类题的通用陷阱严格小于。a[j] a[i] 才计数相等不算。如果你写 样例可能没问题但遇上大量重复可爱值直接错。只统计左侧。不能把自己算进去也不能统计右边。可爱值可能是负数。这就意味着不能直接开一个“值域大小”的数组去计数如果要用树状数组必须离散化而归并排序天然不需要管值域。2. 暴力写法能过样例但大数据必挂先给一段最直白的 Java 实现很多初学者第一反应就是它import java.util.Scanner; public class FishCompareBrute { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { int cnt 0; for (int j 0; j i; j) { if (a[j] a[i]) { cnt; } } if (i 0) { sb.append( ); } sb.append(cnt); } System.out.println(sb); } }逻辑没毛病复杂度也很明确两层循环总比较次数是 0 1 2 ... (N-1)也就是 N*(N-1)/2。N1000约 50 万次比较瞬间出结果。N5000约 1250 万次比较Java 大概几百毫秒到 1 秒能接受。N50000约 12.5 亿次比较必超时。N100000约 50 亿次比较想都别想。在蓝桥杯这类竞赛场景里N 一旦到 10^5暴力就是“样例过、评测超时”的典型死法。所以暴力代码的正确用途是小数据验证、写对拍程序、给优化版本做正确性对照。别指望它拿满分。3. 归并排序解法把“左侧小于”变成归并时的计数核心思路其实一句话归并排序在合并两个有序区间时左半区间的所有元素在原数组里都排在右半区间前面。所以当右半区间的某个元素被放进临时数组时左半区间里已经弹出去的元素就是它左边比它小的元素。这句话听起来有点绕我拆开解释。假设当前正在合并区间 [l, mid] 和 [mid1, r]。这两个子区间已经被分别排好序了而且左半区间的下标全部小于右半区间的下标。归并的标准写法是两个指针 i、j 分别指向左右两个区间的头部谁小谁先进临时数组。我们稍微改一下规则当 a[i] a[j] 时说明左半当前元素比右半当前元素小把左半元素放进临时数组i。当 a[i] a[j] 时说明右半当前元素比左半当前元素小或相等。这时把右半元素放进临时数组同时把答案累加ans[原下标] (i - l)。为什么是 i - l因为左半区间从 l 到 i-1 的元素都已经弹出它们全部严格小于当前这个右半元素。我们不需要逐个去判断数量直接就是 i-l。这里必须强调“严格小于”因为弹出左半的条件是 a[i] a[j]等于的情况下左半不会被弹出。完整代码我贴出来这个版本是直接可提交的import java.util.Scanner; public class FishCompareMerge { static int[] a; static int[] pos; static long[] ans; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); a new int[n]; pos new int[n]; ans new long[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); pos[i] i; } mergeSort(0, n - 1); StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { if (i 0) { sb.append( ); } sb.append(ans[i]); } System.out.println(sb); } static void mergeSort(int l, int r) { if (l r) { return; } int mid (l r) 1; mergeSort(l, mid); mergeSort(mid 1, r); merge(l, mid, r); } static void merge(int l, int mid, int r) { int[] tmpA new int[r - l 1]; int[] tmpPos new int[r - l 1]; int i l; int j mid 1; int k 0; while (i mid j r) { if (a[i] a[j]) { tmpA[k] a[i]; tmpPos[k] pos[i]; i; } else { ans[pos[j]] i - l; tmpA[k] a[j]; tmpPos[k] pos[j]; j; } k; } while (i mid) { tmpA[k] a[i]; tmpPos[k] pos[i]; i; k; } while (j r) { ans[pos[j]] i - l; tmpA[k] a[j]; tmpPos[k] pos[j]; j; k; } System.arraycopy(tmpA, 0, a, l, k); System.arraycopy(tmpPos, 0, pos, l, k); } }注意代码里维护了一个 pos 数组记录每个可爱值对应的原数组下标。因为排序过程中 a 数组会不断变化如果没有 pos最后你根本不知道 ans 里的数字应该输出在哪个位置。4. 用手推一遍样例每个数字的答案是怎么累加的这一步我建议你亲手走一遍比看十遍代码都有用。我用样例 4 3 0 5 1 2 来演示只挑几个关键的合并过程。先看最底层的两个相邻元素的合并。合并区间 [4,5] 时左半是索引 4 的 1右半是索引 5 的 2。1 2所以左半先弹出然后右半 2 弹出时i-l 1于是 ans[5] 加上 1。这一步对应的事实是索引 5 的鱼左边只有一个索引 4 的鱼的可爱值 1 比 2 小。再看合并区间 [2,3]左半是 0右半是 5。0 5左半弹出右半 5 弹出时ans[3] 加上 1。这一步对应的事实是索引 3 的鱼在区间 [2,3] 这个范围内左侧只有索引 2 的 0 比 5 小。然后合并更大的区间 [0,3]。此时左半已经排成 3 4原索引 1,0右半已经排成 0 5原索引 2,3。归并过程3 和 0 比3 0 不成立右半 0 弹出ans[2] 0因为左半还没弹出任何元素。3 和 5 比3 5 成立左半 3 弹出。4 和 5 比4 5 成立左半 4 弹出。左半耗尽右半 5 弹出ans[3] 2。于是 ans[3] 之前有 1现在再加 2最终变成 3。这就对上了样例输出。这里有个很关键的理解每个元素并不是在一步之内找到所有左侧小于它的元素而是在不同层级的合并过程中分别把不同区间的贡献累加起来。归并排序天然把整个数组拆成了一棵分治树每个左侧的“远端元素”都会在某个合并层和当前元素相遇一次。如果你只统计全局逆序对总数代码会更简单只需要一个全局计数器不需要 ans 数组按位置累加。但本题要求每个位置的答案所以必须用 ans[pos[j]] 这种方式逐层累加。这也是很多初学者把逆序对模板背得很熟、却在这题上卡住的原因。5. 几个真实的坑从计数溢出到 IO 超时这类题提交时Java 选手最常见的坑有下面几个我基本全踩过。第一个坑ans 用 int 必炸。最坏情况是数组严格递减比如 5 4 3 2 1 0。此时每条鱼左侧都找不到比自己小的总答案不是很大不对严格递减时左侧小于自己的数量全是 0。真正会很大的是数组严格递增比如 0 1 2 3 4 5第 i 条鱼左侧有 i 条比自己小的总答案是 N*(N-1)/2。N100000 时大约是 49.995 亿明显超过 int 上限 21 亿。所以 ans 必须用 long。这是很多人用 int 交上去 WA 的典型原因。第二个坑等于的情况处理。归并时条件必须是 a[i] a[j] 而不是 a[i] a[j]。如果用 那么相等的左半元素会先弹出。等右半元素弹出时i 已经多走了一步相等的元素就会被错误计入答案。拿数组 1 1 来说正确输出应该是 0 0但如果写 第二个 1 会统计到第一个 1输出变成 0 1。这种 bug 在样例不包含重复值时很难发现所以自己测数据时务必加上全相等的用例。第三个坑pos 数组同步维护。归并时如果你只对 a 排序不动 pos那么 ans[pos[j]] 里的 pos[j] 就不再是原数组下标。我建议把 pos 和 a 一起放进临时数组一起覆盖写回。用两个 int 数组比建一个对象数组更省内存在小数据量下差距不明显但 N10^5 时能差出几 MB而且 Java 对象数组的访问开销更高。第四个坑Scanner 在大数据下的性能。如果 N10^5输入本身不算特别大Scanner 勉强能过但竞赛环境里我建议你还是用 BufferedReader 或一个简单的 FastScanner。输出也一样不要 println 一行一个用 StringBuilder 拼好了一次性输出。这个优化几乎是免费的但很多同学忘了。第五个坑临时数组的创建位置。上面代码在每次 merge 都 new 一个新数组N 大时会有大量小对象创建。更稳的写法是在类里开两个全局数组 tmpA、tmpPos长度等于 Nmerge 的时候直接用对应区间。这样不仅快还能避免频繁 GC 带来的抖动。蓝桥杯这种限时环境GC 抖动有时候就是那个“差一点超时”的元凶。再给一个简单自测用例代码写完先用它验证输入 5 1 1 1 1 1 输出 0 0 0 0 0如果输出不是全 0说明等于处理有问题。另一个用例输入 5 5 4 3 2 1 输出 0 0 0 0 0严格递减时每个位置左边都没有比自己小的所以输出全 0。这个用例能帮你判断“逆序对求错方向”的问题。6. 从这道题延伸出去左侧小于、右侧大于、逆序对都是一套逻辑小鱼比可爱本质上是一道一维偏序计数题。什么叫一维偏序就是你有一个序列要统计每个位置之前满足某个大小关系的元素个数。这类题在算法里可以归为三类左侧小于当前数本题。左侧大于当前数反着比或者用左侧总数减去左侧小于等于当前数。全局逆序对数量所有 i j 且 a[i] a[j] 的对数。这三类都能用归并排序做也能用树状数组做。归并排序版本的优点是不需要离散化直接处理原始数值哪怕可爱值有负数、有 10 位数也没关系。树状数组版本优点是代码思路更统一但需要先把数值离散化成排名等于多一步。如果面试官让你现场写我会优先推荐归并排序原因有三个不会因为离散化错误导致越界访问。代码里天然带着稳定性原理讲起来很顺。可以顺手把“如何求全局逆序对”也答出来显得你对分治理解更深。树状数组版本适合这么用题目已经给了值域范围比如可爱值在 0 到 100000 之间不用离散化。此时 BIT 代码很短查询和更新分别是 O(log n)总复杂度一样。还有一种常见变形是“右侧小于当前数”LeetCode 上有一道很经典的题就是这个。方法可以倒过来做从右往左遍历用树状数组维护已经见过的值也可以用归并排序在合并时统计左半元素有多少个大于右半元素。思路和本题基本一致只是方向改了。如果你能把“小鱼比可爱”彻底理解那道题基本就是白送。7. 我的实际体会别急着背模板先搞懂“计数发生在哪一步”这道题我前前后后写过三版。第一版是暴力纯为了对拍。第二版我直接背了逆序对的归并模板结果输出全乱因为模板只统计总数不关心每个位置各自的答案。后来我把归并过程一行行打印出来才真正看明白每个元素和左侧不同区间的比较是分散在多次合并里的必须把答案逐层累加到对应原下标上。从那以后我再遇到“统计每个位置满足某种关系的数量”这类题第一反应就不是套模板而是先想清楚这个关系会在哪个分治步骤里被恰当地观察到。一个小技巧分享给你debug 的时候别打印整个数组在 merge 方法里打一行关键信息就行比如当前 l、mid、r以及每次给 ans[pos[j]] 增加的量。配合小数据马上就能看出计数逻辑哪里不对。最后再说说提交策略。如果题目没有给数据范围或者你拿不准我会把归并版本当成默认答案暴力版本只用来对拍。归并写起来多花两分钟但换来的是从 N5000 到 N100000 都能稳过的安心感。蓝桥杯这种比赛能 AC 和不能 AC 往往就差在“有没有提前想到复杂度”上。小鱼比可爱这道题就是这个道理最好的练习。