题目大意 nnn 个人，每个人身高已知，有 qqq 次询问，找出身高大于等于 xjx_jxj 的人数。 解题思路 对于每次查询，如果都遍历所有人的身高的话，时间复杂度为 O(nq)O(nq)O(nq) ，无法通过。 容易发现对所有人的身高进行排序，那么大于等于 xjx_jxj 的身高就会出现在一段后缀当中，因此容易想到使用二分查找能够快速找出分解点。 时间复杂度 O(nlog(n)+qlog(n))O(nlog(n)+qlog(n))O(nlog(n)+qlog(n)) 。 参考代码

不得不承认官方给的题解还是很简洁明了的，不过在下也可以提供一种新的方法。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 另一种可行思路 建立一个差分数组c，满足 ∑i=1nc[i]=s[i]\displaystyle\sum_{i=1}^{n}c[i]=s[i]i=1∑n c[i]=s[i]，其中 s[i] 是身高大于等于i的人数。 输入一个身高h，只需要将c[h]++，就可以构造出这个差分数组。 输入结束后只需要做c[i]+=c[i-1]遍历进行前缀和即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 操作优化 既然我们需要构建差分数组，并在最后进行前缀和处理，我们可以用树状数组处理，每次输入身高只需要对树状数组相应位置进行+1操作即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 注意事项 由于数据范围 hi,xj≤109h_i,x_j\leq10^9hi ,xj ≤109，如果不加处理就开树状数组会导致爆空间，因此需要对 hih_ihi 和 xix_ixi 进行离散化。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码