数轴上有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<cstdio> 2 #include<iostream> 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<hi){ 10 int mi=(lo+hi)/2; 11 if(num<s[mi]){ 12 hi=mi; 13 }else lo=mi+1; 14 } 15 return --lo; 16 } 17 int getpartition(int lo,int hi){ 18 int mi=s[lo]; 19 while(lo<hi){ 20 while(lo<hi&&mi<=s[hi])hi--; 21 s[lo]=s[hi]; 22 while(lo<hi&&s[lo]<=mi)lo++; 23 s[hi]=s[lo]; 24 } 25 s[lo]=mi; 26 return lo; 27 } 28 29 //快速排序 30 void quicksort(int lo,int hi){ 31 if(lo<hi){ 32 int mi=getpartition(lo,hi); 33 quicksort(lo,mi-1); 34 quicksort(mi+1,hi); 35 } 36 } 37 //注意输入输出太多，所以需要使用scanf,printf 加速输入输出 38 int main(){ 39 scanf("%d%d",&m,&n); 40 for(int i=0;i<m;i++){ 41 scanf("%d",&s[i]); 42 } 43 quicksort(0,m-1); 44 int a,b; 45 for(int i=0;i<n;i++){ 46 scanf("%d%d",&a,&b); 47 int resA=binSearch(a-1,0,m);//小于a的最后一个位置 48 int resB=binSearch(b,0,m);//b的最后位置 49 printf("%d \n",resB-resA); 50 } 51 return 0; 52 }
原文：https://www.cnblogs.com/Yvettey-me/p/9503255.html
