2016 Silver December p1

Posted on In , ,

题目

给出一个长度为 N 的数列和 M 个范围（1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000），分别求出数列中有多少个数在范围内。

思路

先将数列排序，用二分法分别找出数列中对应数字的 index，再用上界的 index 减下界的 index

复杂度分析

排序的复杂度为 N logN，对 M 个范围分别用二分法的复杂度为 M logN，总复杂度最大为 10^5 log(10^5)，不会超时