最近开学了，又复习了下数据结构与算法，我在MOOC上学的。这次是清华oj平台上的一题。
题目：范围查询(Range)
Descriptioin
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
代码一
第一个解决方案是去年刚看到这题根据课程写的代码：
/*VC++6.0PA1 – RangeAsk.cppTsinghua Data Structures & Algorithmsby zerolevaat 2014-10-19*/#include <stdio.h>#define _OJ_const int MAX_SIZE = 500005;//0 ≤ n, m ≤ 5×10^5,点的总数void MSort(int [], int, int);//归并排序void Merge(int [], int, int, int);//合并int BSearch(const int [], int, int, bool&);/* 折半查找，找到则返回元素下标找不到时，若查找的值小于所有元素则返回-1,否则返回不大于它的最大元素的下标*/int main(){#ifndef _OJ_freopen(“input.txt”, “r”, stdin);//freopen(“output.txt”, “w”, stdout);#endifint m, n, i;int* point = new int[MAX_SIZE];//在堆上分配大的数组scanf(“%d %d”, &n, &m);for (i=0; i<n; i++){scanf(“%d”, &point[i]);//输入所有坐标}MSort(point, 0, n);//排序，O(nlogn)while (m–){int a, b;scanf(“%d %d”, &a, &b);bool find_b = false;bool find_a = false;int cnt = (b<point[0] || a>point[n-1]) ?0 : (BSearch(point, n, b, find_b) – BSearch(point, n, a, find_a)); //直接相减，，O(2logn)cnt = find_a ? cnt+1 : cnt;//由于BSearch返回不大于被查找值的最大元素下标//判断a是否找到，若找到需要将cnt加1printf(“%d\n”, cnt);}#ifndef _OJ_fclose(stdin);//fclose(stdout);#endifreturn 0;}void MSort(int a[], int lo, int hi){if (hi-lo < 2){return ;}int mi = (lo+hi) >> 1;MSort(a, lo, mi);MSort(a, mi, hi);Merge(a, lo, mi, hi);return ;}void Merge(int a[], int lo, int mi, int hi){int* A = a+lo;int i;int lb = mi-lo;int* b = new int[lb];//新建一个b数组存a中lo-mi的元素for (i=0; i<lb; i++){b[i] = A[i];}int lc = hi-mi;int* c = a+mi;//用新指针c标识mi-hi的元素int j, k;for (i=0,j=0,k=0; (j<lb) && (k<lc); i++){//比较b数组以及c数组元素大小，并将其中小的存入原数组a//直到其中一个数组比较完A[i] = (b[j] <= c[k]) ? b[j++] : c[k++];}while (j<lb)//若c先比较完，则剩下的b数组中的元素都是大的，复制进原数组后面{//若b先比较完，不必将c复制进a，因为c本就是a的A[i++] = b[j++];}delete []b;return ;}int BSearch(const int a[], int n, int x, bool& find){int lo=0, hi=n;int mi;while (lo < hi){mi = (lo+hi) >> 1;if (a[mi] == x){find = true;//找到则将find改为truereturn mi;//找到则返回该元素下标}else if (x < a[mi]){hi = mi;}else{lo = mi+1;}}return –lo;//没找到时，返回不大于被查找值的最大元素下标}
当时写的坑坑洼洼的，不过大体思路很清晰：输入，排序，查找，计算。这里排序和查找用的是归并排序以及二分查找，具体的见代码，有注释。
代码二#include <stdio.h>#include <string.h>#define MAXN 500005#define MAXNUM 10000005int n, m;int BSearch(const int sorted[], int x);//折半查找，返回不大于所查找数字的元素的下标 int main(){scanf(“%d %d”, &n, &m);int* sorted = new int[MAXN]; //存储已排序的数char* p = new char[MAXNUM];memset(p, 0, sizeof(p)/sizeof(char));int max=0;int i;for (i=0; i<n; i++){int tmp;scanf(“%d”, &tmp);p[tmp] = 1;//若输入数字num，则p[num]=1，否则p[num]=0max = (tmp<max) ? max : tmp;}//排序//由0-max，用sorted数组储存排序的数字int j=0;for (i=0; i<=max; ++i){if(1 == p[i]){sorted[j++] = i;}}//由于坐标互异，排序完后应该j==n-1while(m–){int cnt = 0;int a, b;scanf(“%d %d”, &a, &b);int pA = BSearch(sorted, a);int pB = BSearch(sorted, b);cnt = pB-pA;cnt = (pA >= 0 && a == sorted[pA]) ? cnt+1 : cnt;//判断a是否找到，若找到需要将cnt加1//printf(“pA=%d && pB=%d\n”, pA, pB);if(0 == n){printf(“0\n”);continue;}printf(“%d\n”, cnt);}return 0;}int BSearch(const int sorted[], int x){int lo=0, hi=n;while(lo < hi){int mid = (lo+hi) >> 1;if(sorted[mid] == x){return mid;}else if(x < sorted[mid]){hi = mid;}else{lo = mid+1;}}// printf(“%d\n”, lo);return –lo;}
这个是现在写的，投机取巧了点。这里没有用归并排序，写起来太麻烦。利用了各坐标点互异这个因素，具体看代码。其他的还是跟代码一一样的。
主要说一下写这段代码时主要遇到的bug：
第33行那里的j忘记赋初值。其实之前是赋值了的，只是修改代码后忘了赋初值，由于没有重新编译，用的是之前的中间代码，导致递交了好几次没有赋初值的错误代码。下次要谨记修改后重新编译！
第55行那里原本的代码是这样的： cnt = (a == sorted[pA]) ? cnt+1 : cnt; 没有判定pA>=0，导致提交后总是有三个测试数据过不掉。至于为什么加这个→_→大家自己想想~
代码三往事是尘封在记忆中的梦，而你是我唯一鲜明的记忆，
