范围查询(Range)
Description
Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are asked to count the points lying inside.
Input
The first line contains two integers: n (size of S) and m (the number of queries).
The second line enumerates all the n points in S.
Each of the following m lines consists of two integers a and b and defines an query interval [a, b].
Output
The number of points in S lying inside each of the m query intervals.
Example
Input
5 2
1 3 7 9 11
4 6
7 12
Output
0
3
Restrictions
0 <= n, m <= 5 * 10^5
For each query interval [a, b], it is guaranteed that a <= b.
Points in S are distinct from each other.
Coordinates of each point as well as the query interval boundaries a and b are non-negative integers not greater than 10^7.
Time: 2 sec
Memory: 256 MB
描述
数轴上有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
本来想用树状数组做，后来发现二分查找+归并排序就可以了，贴代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include<cstdio> #include<cstdlib> using namespace std; void Merge(int *a,int s,int m,int e,int *b){ int ptr1=s,ptr2=m+1,ptr=s; while (ptr1<=m&&ptr2<=e){ if (a[ptr1]<a[ptr2]) b[ptr++]=a[ptr1++]; else b[ptr++]=a[ptr2++]; } while (ptr1<=m){ b[ptr++]=a[ptr1++]; } while (ptr2<=e){ b[ptr++]=a[ptr2++]; } for(int i=s;i<=e;i++){ a[i]=b[i]; } } void MergeSort(int *a,int s,int e,int *b){ if(s<e){ int m=s+(e-s)/2; MergeSort(a,s,m,b); MergeSort(a,m+1,e,b); Merge(a,s,m,e,b); } } int BinarySearch(int * Array,int low,int high,int value){ //[low,high) int mid; while(low<high){ mid=(low+high)/2; if(value<Array[mid]){ high=mid; }else if(Array[mid]<value){ low=mid+1; }else{ return mid; } } return mid; } int getRealpos(int * Array,int n,int oldpos,int value,char type){ if(type=='l'){ while(oldpos<n&&Array[oldpos]<value)oldpos++; //l是value本身或比value大的第一个数 }else if(type=='h'){ while(oldpos>=0&&Array[oldpos]>value)oldpos--; //h是value本身或比value小的第一个数 } return oldpos; } int num(int * Array,int n,int low,int high){ int start=BinarySearch(Array,0,n,low); int end=BinarySearch(Array,0,n,high); start=getRealpos(Array,n,start,low,'l'); end=getRealpos(Array,n,end,high,'h'); return end-start+1; } int main(){ int n,m; scanf("%d %d",&n,&m); int * array=new int[n]; int * arrayt=new int[n]; for(int i=0;i<n;i++){ scanf("%d",array+i); } MergeSort(array,0,n-1,arrayt); for(int i=0;i<m;i++){ int lo,hi; scanf("%d %d",&lo,&hi); int re=num(array,n,lo,hi); printf("%d\n",re); } delete [] array; delete [] arrayt; } |