数据结构 邓俊辉 PA#1 范围查询(Range) 题解

范围查询(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;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注