描述

数轴上有n个点，对于任一闭区间 [a, b]，试计算落在其内的点数。

输入

第一行包括两个整数：点的总数n，查询的次数m。

第二行包含n个数，为各个点的坐标。

以下m行，各包含两个整数：查询区间的左、右边界a和b。

输出

对每次查询，输出落在闭区间[a, b]内点的个数。

样例

见英文题面

限制

0 ≤ n, m ≤ 5×105

对于每次查询的区间[a, b]，都有a ≤ b

各点的坐标互异

各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数

时间：2 sec

内存：256 MB

 

题意：给一堆可能无序的点，查找落在【a,b】区间的点个数

思路：无序点使用快速排序改为有序序列，然后使用二分查找查找a,b的位置

注意（1）查找的是小于a的最大的位置，查找的是b的最大的位置，相减即可

（2）输入输出使用scanf，printf，否则会超时

代码如下：

1 #include
       
         2 #include
        
          3 using namespace std; 4 int s[500005]; 5 int m,n; 6  7 //二分查找,返回不大于num的最后一个元素 8 int binSearch(int num,int lo,int hi){ 9     while(lo