Tsinghua OJ 范围查询( Range )问题

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


问题描述


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

输入


第一行包括两个整数:点的总数n,查询的次数m。
第二行包含n个数,为各个点的坐标。
以下m行,各包含两个整数:查询区间的左、右边界a和b。

输出


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

样例

Input
5 2
1 3 7 9 11
4 6
7 12

Output

0
3

限制
0 ≤ n, m ≤ 5×105
对于每次查询的区间[a, b],都有a ≤ b
各点的坐标互异
各点的坐标、查询区间的边界a、b,均为不超过10^7的非负整数
时间:2 sec
内存:256 MB

分析


开始看到这个题时,没想太多,直接用简单的循环来尝试,试了好几次才发现完全不对…Google一下,才发现想得太简单了,要先考虑数组的有序性问题,才能再来考虑查找,而且既然是DSA的课程,肯定就要用DSA的方法来解决。
本题的解题思路是,先通过C++中cstdlib的qsort方法来给输入的n个数进行排序,再在已排序好的数组进行,查找分两次,一次是最小值在数组中的序,另一次是最大值,两者相减即为本题所求的个数,这其中还有一个小坑。

首先是qsort排序,把输入的n个点进行有序排列,方便后续进行。其函数原型为:

void qsort(void *base, int nelem, unsigned int width, int ( * pfCompare)( const void *, const void *));

而针对此题的具体qsort方法是:

qsort(dot, n, sizeof(int), compare);

vector为n个点的数组,n即n个点的个数,sizeof(int)是待排序数组的元素大小, compare为自己编写的一个比较函数,此处为:
1
2
3
4
compare(dot * int a, const * int b)
{
return ( * ( int *) a, * ( int *) b);
}


其中* ( int **) a的含义:是 a是一个指针类型,(int *)a表示将a转换为int型指针,然后*(int *)a就表示取a指针指向的地址的值,并且是以int型来取,结果为一个int,b同a。最后返回两值之差。关于qsort更详细的使用方法可以参考这里

把n个数的 dot 数组进行排序后,接下来就是在其中查找符合闭区间[a, b]的个数。这里就要开始使用二分查找,简单的思路是先左查找 a 的序,再又右查找 b 的序,然后右查找的序减去左查找的序即为其中的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
int binSearch( int lo, int hi, int *p ,  int e)
{
while ( lo < hi)
{
int mi = ( lo + hi ) >> 1;
( e < p[mi] ) ? hi = mi : lo = mi + 1;
}
return --lo;
}
left = binSearch(0, n, dot, a );
right = binSearch(0, n, dot, b);
if( dot(left) == a && left >= 0) letf --;
for(i = 0; i < m; i++) result[i] = right - left;


这里最容易疏忽掉的一点是,左边查找的 dot(letf) 与 左边边界 a 是不是重合,如果重合,那么计算 right - letf 就会发现,会把边界 a 漏掉,其值比正常计算少了1。通过letf – 即可解决问题,但是新问题是,如果计算出的 letf 为-1, 即表示查找的 a 并不在 dot 中,比最小值还小,这样计算的话就不用考虑dot(left) 与 a 重合的问题了,直接计算即可。所以,要在输出值之前,加上 if (dot (left) == a && left >= 0) left –; 来排除掉这种可能性。
实际运行情况来看,10次测试可以全部correct,但是运行时间还有待提高,可能还需要整体再优化。

源代码

github