1. 先搞清楚“比自己强的人数”到底在问什么
1.1 从赛题描述到可计算的模型
前两天在某个在线评测平台上刷题，看到一道分值200分的题目，题面写得非常简短：“给定一个整数序列，对于序列中的每个元素，请统计序列中有多少个数严格大于它。”语言限制是Java、JavaScript、Python三选一。当年第一次遇到这类题的时候，我脑子里冒出来的第一个念头是：这题不是O(N²)直接双重循环就完事了吗？但等我真正把数据范围看清楚，才发现这个200分一点都不白给。
先把这个题翻译成人话。假设现在有5个人的得分分别是[90, 85, 90, 70, 100]，那么对于第一个人（90分），比他强的人就是得分严格大于90的人，这里只有100这一个，所以答案是1；对于第三个人（同样也是90分），比他强的还是只有100，答案也是1；没有人比自己强，这里的“比自己强”必须是严格大于，也就是说相同分数的两个人互相不算“比自己强”，这是题目里最容易忽略的隐含条件。输出的时候，需要按原序列的顺序，依次输出每个人的“更强人数”，例如上面的例子输出就是1 2 1 4 0。
我把这道题当作一个典型的“排名统计”问题来理解，因为在实际业务里这个场景实在太常见了：游戏服务器要算每个玩家在全区里的战力排名，赛事系统要算每支队伍在小组中的胜场排名，甚至一些社交产品里“你超过了多少好友”的文案背后，也是同一套计算逻辑。把这个题吃透，并不只是为了拿那200分，而是为了掌握一类统计问题的基础切入点。
1.2 样例推演：严格大于与相等的处理
为了把边界条件彻底弄清楚，我习惯先用手工推演一个小例子。假如序列是[90, 85, 90, 70]，把它按降序排好，就是[90, 90, 85, 70]。
逐个来看。对于第一个90，降序序列里从头开始扫描，第一个严格大于90的元素不存在，所以更强人数是0。对于85，降序序列里严格大于85的元素是前面两个90，所以是2。对于70，前面三个元素90、90、85都大于70，所以是3。整个答案就是[0, 2, 0, 3]。
这里有两个教训：第一，两个90的存在感完全不同，它们都不比对方“强”，所以在统计时要保证相等分数不会被计入“更强人数”；第二，降序排序只是方便我们利用有序性做二分查找，而不是简单地输出下标。很多同学第一次写这题，直接把分数降序排序后，对每个元素输出它在排序数组里的下标，这是错的——遇到重复值的时候，下标会把那些和自己同分的人也当成“比你强”的人。
严谨的模型是：对于每个元素x，它的答案等于“所有严格大于x的元素个数”，在降序数组中，这个值恰好等于“第一个小于等于x的元素的下标”。为什么？因为降序数组里，下标0到k-1这一段元素全都严格大于x，而k位置开始就不再大于x了，所以k就是我们要的计数。
1.3 数据范围决定了你能用什么算法
做算法题第一件事不是写代码，而是看数据范围。这道200分的题，N最大可以到10⁵级别，值域则可能去到10⁹级别的随机整数。如果不是这个范围，我可能真会推荐你直接暴力：
对于每个元素 x： 遍历整个数组，统计大于 x 的个数时间复杂度O(N²)，N=10⁵时就是10¹⁰次比较，跑完需要几分钟甚至更久，评测机不可能给你这种复杂度通过。N=1000以内倒是完全没问题，但既然分值给了200分，出题人显然是想考核“排序+二分”这类O(N log N)的思路，或者进一步考核树状数组离散化这类O(N log N)但扩展性更强的做法。所以在动手之前，先把范围看清楚，这决定了你后面所有的实现细节。
2. 暴力解与排序二分：两条路线的推导
2.1 为什么暴力会挂掉
我不止一次见过有人在这个题上交暴力代码，理由也很朴素：“统计比自己大的数，不是一眼就能看出来的嘛，两层循环嘛。”对于小范围的数据，比如N=100、值域不超过1000，暴力不仅能过，而且代码好写好调。但问题在于，这类题出现在200分的档位，数据几乎一定会卡O(N²)。
暴力代码大概长这样：
def brute(arr): n = len(arr) res = [] for i in range(n): cnt = 0 for j in range(n): if arr[j] > arr[i]: cnt += 1 res.append(cnt) return res它的问题在于大量重复计算。对于每个元素，它都把整个数组重新扫一遍，而这些扫描之间没有任何信息复用。比如你已经知道85前面有两个90，那在统计70的时候，其实可以直接复用“有多少人大于85”再加上“有多少人介于70和85之间”的信息，但暴力解把这些信息全都扔掉了。
我倾向于把暴力解当作一个“正确性基准”来使用。写正解之前，先写一个暴力版本，用小数据对照验证，这样可以在调试时快速排查排序、二分里是不是写错了。
2.2 排序后“比自己强”就是“第一个小于等于出现的位置”
主解法的核心观察是：当你把所有分数按降序排好后，每个元素在有序数组中的位置已经隐含了所有统计信息。设降序数组为sorted_arr，那么“严格大于x”的人数等于sorted_arr中小于等于x的第一个位置的下标值。
举个例子会更直观。还是[90, 85, 90, 70]，降序后是[90, 90, 85, 70]。我要统计85的答案，二分找到第一个小于等于85的位置，从左往右扫描：90大于85，90大于85，85不大于85，所以这个位置是2，答案就是2。再统计70，找到第一个小于等于70的位置是3，答案就是3。
为什么“第一个小于等于”这个位置刚好就是答案？因为降序数组中，位置0到pos-1的元素都严格大于x，它们恰好就是“比自己强的人”。而位置pos以及之后的所有元素都不再大于x，不能再算进去。所以答案等于pos，不是pos+1也不是pos-1。这里有一个很多初学者会犯的经典错误：直接用二分查找模板在排序数组里找一个恰好等于x的位置，然后返回这个位置的下标，这在有重复值时会出现偏差，因为第一个等于x的位置往往不是第一个小于等于x的位置。
处理的关键在于二分查找的判定条件。我常用的模板是：
lo = 0, hi = n while lo < hi: mid = (lo + hi) // 2 if sorted_arr[mid] > x: lo = mid + 1 else: hi = mid 答案 = lo这个循环结束时，lo指向的位置满足：它左边全是严格大于x的元素，它自己以及右边全是小于等于x的元素，于是lo就是答案。这个模板是基于“寻找第一个小于等于x的位置”来写的，一开始容易搞反，我建议你把它背下来，然后多手推两个有重复值的例子验证。
2.3 复杂度对比
排序的时间复杂度是O(N log N)，二分查找每个元素是O(log N)，N个元素总共O(N log N)，整体就是O(N log N)。空间上需要一个排序后的副本数组，O(N)。对比暴力的O(N²)，当N=10⁵时，O(N²)要执行约5×10⁹次内层操作，而O(N log N)大概是1.7×10⁶次操作，差距是三个数量级。这也是为什么所有像样的算法课程都会反复强调排序的价值：排序一次，后面所有查询都能享受对数级别的快速查找。本质上，这题就是在考“如何预处理数据来支持多次查询”。
3. 三种语言的AC实现与输入输出细节
3.1 Java版：包装类排序与手写二分
Java的排序API有一个让很多人抓狂的细节：对基本类型数组int[]进行降序排序，不能直接传Collections.reverseOrder()，因为这个比较器只能作用于对象数组。所以你有两条路：要么把int[]转成Integer[]再排序，要么干脆升序排序后从尾部往前二分。
实测下来我更喜欢手写二分的方案，因为Arrays.binarySearch在重复元素和降序数组上的行为并不直观，容易踩坑。下面这个版本是我在OJ上调通的：
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Integer[] arr = new Integer[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } Integer[] sorted = arr.clone(); Arrays.sort(sorted, (a, b) -> b - a); // 降序 StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { int x = arr[i]; int lo = 0, hi = n; while (lo < hi) { int mid = (lo + hi) >>> 1; if (sorted[mid] > x) { lo = mid + 1; } else { hi = mid; } } if (i > 0) sb.append(' '); sb.append(lo); } System.out.println(sb); } }注意几个细节。第一，(lo + hi) >>> 1是为了防止当lo + hi溢出变成负数，在数组长度很大的时候这个写法更安全。第二，排序用的lambda表达式(a, b) -> b - a在数据范围很大会有溢出风险，比如b是10⁹、a是-10⁹时，b - a会溢出成负数导致排序异常。更稳妥的写法是(a, b) -> Integer.compare(b, a)。第三，用StringBuilder拼接输出而不是逐次System.out.print，是为了避免大量IO操作拖慢运行速度，实测在N=10⁵时这个优化能省不少时间。
3.2 Python版：读入技巧与列表推导
Python写这类题，最大的优势是代码短，最大的坑是输入输出格式和排序默认行为。看一个能直接提交的版本：
import sys def main(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return n = data[0] arr = data[1:1 + n] sorted_arr = sorted(arr, reverse=True) res = [] for x in arr: lo, hi = 0, n while lo < hi: mid = (lo + hi) // 2 if sorted_arr[mid] > x: lo = mid + 1 else: hi = mid res.append(str(lo)) sys.stdout.write(" ".join(res)) if __name__ == "__main__": main()sys.stdin.buffer.read().split()是我推荐的读入姿势。它一次性把整个标准输入读进来，按空白字符切分，比逐行input()快很多，在N=10⁵时差异很明显。这里我还想多说一句：Python的列表推导式虽然优雅，但在这个二分循环里强行用推导式反而会把逻辑绕晕，不如老老实实写for循环，可读性优先。
如果你用Python的bisect模块，也不是不行，但要小心方向问题。bisect_right(sorted_arr, x)在降序数组上是没法直接使用的，因为bisect系列默认升序语义，你传降序数组进去会得到很奇怪的结果。我试过把数组存成负数升序，然后用bisect_right，那又是另一种绕法。既然手写二分只有四五行，我更建议直接手写，逻辑透明，不容易记错。
3.3 JavaScript版：sort默认字典序是个深坑
JavaScript版是三种语言里最容易出“灵异事件”的，罪魁祸首就是Array.prototype.sort()。我之前在一道题里写过arr.sort()，然后惊喜地发现[10, 9, 100, 2]被排成了[10, 100, 2, 9]，当时整个人都懵了。查了文档才想起来：JS的sort默认把元素转成字符串后按字典序排序，数字比较必须显式传比较器。正确写法是：
const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); const lines = []; rl.on('line', line => lines.push(line.trim())); rl.on('close', () => { const data = lines.join(' ').split(/\s+/).map(Number); const n = data[0]; const arr = data.slice(1, 1 + n); const sorted = [...arr].sort((a, b) => b - a); const res = arr.map(x => { let lo = 0, hi = n; while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (sorted[mid] > x) lo = mid + 1; else hi = mid; } return lo; }); console.log(res.join(' ')); });输入处理上，我先把所有行收集起来再统一切分，是因为竞赛环境里数据可能分布在多行，按行逐行处理容易漏掉跨行的数组元素。const sorted = [...arr].sort(...)是为了不修改原数组，因为后面统计时还需要原顺序。这里Math.floor((lo + hi) / 2)和Java的>>>1作用一样，防止整数溢出（JS虽然数字都是浮点，但位运算会转成32位整数，所以用Math.floor更直观）。
我还想给JS版一个建议：如果N很大，回调函数里的比较器会被调用很多次，性能敏感时可以先用Uint32Array之类的类型化数组，但一般OJ环境用普通数组就够了，不必过度优化。真正要注意的是把map、join这些数组操作用好，因为它们比显式for循环更容易保证不越界。
4. 树状数组与离散化：从“静态统计”到“动态维护”
4.1 什么时候才需要树状数组
排序+二分解法的局限性在于：它要求所有数据一次性给出，而且查询过程是静态的，不能在处理过程中动态插入新的人。如果题目改成“每次加入一个分数，立即查询当前有多少人比自己强”，排序+二分就变得很别扭，因为每次插入都要重新排序，复杂度退化到O(N² log N)。这时候就需要一种支持动态插入和动态查询的数据结构，树状数组就是最常见的方案。
另外，排序+二分的答案依赖原数组的完整结果，无法在数据流场景下边接收边输出。所以在一些变种题里，即使N不大，用树状数组也会让代码的扩展性更好。我通常会在脑子里做一个决策：只有查询，就用排序+二分；有动态插入，或者需要在线处理，就用树状数组。
4.2 离散化压缩值域
树状数组的索引是整数，但分数可能是10⁹级别的，不可能直接开一个10⁹大小的数组。离散化的思路是把“具体的分数”映射成“这个分数在所有不同分数中的排名”。假设分数是[90, 85, 90, 70, 100]，不同分数排序后是[70, 85, 90, 100]，那么70映射为1，85映射为2，90映射为3，100映射为4。压缩之后，值域大小M最多等于N，空间就变成了O(N)。
离散化的代码很简单：
vals = sorted(set(arr)) rank = {v: i + 1 for i, v in enumerate(vals)}4.3 倒序插入的代码与推导
树状数组统计“比自己强的人数”，等价于统计“已插入元素中严格大于当前元素的个数”。如果从右往左遍历原数组，那么在处理arr[i]时，已经插入的恰好是原数组中所有在它右侧的元素。右侧元素中严格大于它的个数，就等于“已插入总数减去已插入元素中小于等于它的个数”。
实现时，树状数组的每个位置维护某个离散化值出现的次数，“小于等于某个值的个数”就是树状数组的前缀和。完整代码：
class BIT: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def add(self, idx, val): while idx <= self.n: self.tree[idx] += val idx += idx & -idx def sum(self, idx): s = 0 while idx > 0: s += self.tree[idx] idx -= idx & -idx return s def stronger_count(arr): vals = sorted(set(arr)) rank = {v: i + 1 for i, v in enumerate(vals)} bit = BIT(len(vals)) res = [0] * len(arr) total = 0 for i in range(len(arr) - 1, -1, -1): r = rank[arr[i]] res[i] = total - bit.sum(r) # 已经插入的右侧元素里，严格大于当前值的个数 bit.add(r, 1) total += 1 return res为什么total - bit.sum(r)算出来的是严格大于而不是大于等于？因为bit.sum(r)统计的是离散化后排名不大于r的所有已插入元素的数量，也就是所有小于等于当前分数的右侧元素数量。用已插入总数减去它，剩下的就是严格大于当前分数的右侧元素数量。这个逻辑链需要你亲手推一遍重复值的情况：两个90分先后被处理，先处理的右边那个90先插入，后处理的左边那个90在查询时，已插入的右边90虽然和它同分，但因为同分的90也落在bit.sum(r)里，所以不会被算进“更强人数”，正好符合题意。
树状数组单次插入和查询都是O(log M)，M是不同分数的个数，整体复杂度O(N log N)。虽然和排序+二分复杂度同阶，但它支持在任意时刻插入新元素，这是静态排序方案做不到的。如果你在面试里被追问“如果数据是流式的怎么办”，能接出这个解法是一个明显的加分项。
5. 实测踩坑清单与三道题通用经验
5.1 典型错误一：把小于等于算成了小于
这个错误最隐蔽。有人在二分时把判定条件写成if (sorted[mid] >= x) lo = mid + 1; else hi = mid;，意思是寻找“第一个小于x的位置”。对于没有重复值的用例，这两种写法答案一样，因为不存在等于x的元素。一旦出现重复值，比如[90, 85, 90, 70]，后一个90就会被统计成有1个比自己强的人——其实是左边那个90，这就错了。我在本地用小数据测试时，因为输入样例没有重复值，第一次提交都AC了，后来自己补了重复值测试才发现这个隐患。
建议是：在本地准备一个专门的“重复值暴力对拍脚本”，生成随机小数组，暴力计算标准答案，和你的正解输出对比。对拍几次，这种边界问题基本都能暴露。
5.2 典型错误二：二分边界差一个
二分的边界是另一个高频翻车点。我看过有人把hi初始化为n - 1，然后循环条件写lo < hi，结果所有元素都大于目标值时，答案总会少1；有人把mid = (lo + hi) // 2的更新逻辑写对称，导致死循环。正确的模板是左闭右开区间[0, n)，循环不变量是“答案在[lo, hi)内”，这样初始化lo = 0, hi = n最安全。
如果你不想依赖这个模板，也可以用一种更“傻瓜”的方式：先用java.util.Arrays.binarySearch一类API找插入点，但我劝你别这么干。手写二分的模板最多5行，背下来比记忆API在各种边界情况下的行为可靠得多。我自己的习惯是把这套“寻找第一个不满足某条件的位置”的模板抄在笔记本上，遇到类似题直接套。
5.3 典型错误三：JS的sort与Java基本类型排序
JS的sort默认字典序我已经说过了。Java的Arrays.sort(int[])倒是不会字典序，但它默认升序，你想降序又不能直接传比较器。很多同学在Java里试图写Arrays.sort(sorted, Collections.reverseOrder())，结果编译报错，因为Collections.reverseOrder()只能用于对象数组。解决方案是改用Integer[]，或者索性升序排序后在二分里做镜像处理。
我还见过一个Java的坑：Integer.compare(a, b)和a - b的区别。在Arrays.sort(Integer[], Comparator)里用b - a做比较器，当b是Integer.MIN_VALUE、a是Integer.MAX_VALUE时会溢出，导致排序结果错误。不要偷懒，Comparator里一律用Integer.compare或Comparator.reverseOrder()。
5.4 刷题策略：如何在200分题里练出300分的能力
这类题的价值不在AC本身，而在于一题多想。我把这道题按难度分了三个层次：第一层，能想到排序+二分并写出来；第二层，能处理重复值、大值域、三种语言差异等各种边界；第三层，能迁移到树状数组和离散化，甚至在面试场景里讲清楚“为什么不用暴力”。
一个我常用的练习方法是：AC之后，强制自己用另一种数据结构重写一遍。比如这题，先用排序+二分写一遍，再用树状数组写一遍，最后把两种解法放到本地数据生成器上做性能对比。经过这样一轮，下次再遇到“统计右侧有多少元素大于当前值”“逆序对个数”这些经典变种题时，你会发现自己对有序性和数据结构之间关联的敏感度明显提高了。
还有一个实用技巧：输出格式永远用“空格分隔、末尾不补空格”的规范来拼串。评测系统对行末空格的处理各有不同，有的会报Presentation Error，虽然不影响判据，但会白白浪费一次提交。用StringBuilder拼串或者join是最稳妥的。
最后说点实际的体会。在OJ上，一道200分的题往往意味着“给你20分钟想出思路、40分钟写对代码”。我第一次做类似的统计题时，光在二分边界上调了半小时，后来发现其实就是把>=写成了>。从那以后，我给自己定了个规矩：写完任何二分，先用重复值最小的数据跑一遍，再跑一个所有值相等的数据，比如[5,5,5,5]，预期输出应该是0 0 0 0。这一条简单的自测习惯，帮我省下了无数次的错误提交。如果你也正在刷题，建议把这道题当作一个起点，认真把它彻底吃透，因为你后面会遇到的所有“逆序对”“排名统计”“右侧大数数量”类题目，核心骨骼都是从这里长出来的。
