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

描述

数轴上有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

OJ地址:https://dsa.cs.tsinghua.edu.cn/oj/course.shtml?courseid=58

这是清华大学数据结构MOOC的配套练习的第一题,一开始看到这题以为很水,后来我就哭了。。。终究是我太弱。

思路是利用二分查找的一个改进,在有序数组中找到≥a的第一个元素和≤b的最后一个元素。

二分查找的改进的具体分析参见《数据结构邓俊辉第三版》P56

首先我是用Java写了一个O(n)的版本,结果发现纳尼?连一半的测试用例都通不过就会超时。然后写了二分查找的版本,还是只能得60分,这可是个O(logn)的算法呀。平时写leetcode的时间限制太松了,都几乎不会碰到超时的情况。优化之后Java的版本最高得了80分。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int findLeftIndex(int[] nums, int target, int lo, int hi) {
        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            // 若target <= nums[mid],hi = mid,在[lo, mid)中找
            // 若target > nums[mid],lo = mid + 1,在(mid, hi)中
            if (nums[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo; // 循环结束时,lo为>=target的最小下标,故lo-1为<target的最大下标
    } // 有多个元素命中target时,保证返回下标最小的;查找失败时返回>=target的最小下标

    public static int findRightIndex(int[] nums, int target, int lo, int hi) {
        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);

            //int mid = lo + ((hi - lo) >> 1);
            if (nums[mid] > target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }

        }
        return --lo; // 循环结束时,lo为>target的最小下标,故lo-1为<=target的最大下标
    } // 有多个元素命中target时,保证返回下标最大的;查找失败时返回<=target的最大下标


    public static int range(int[] nums, int length, int a, int b) {
        int loRange = findLeftIndex(nums, a, 0, length);
        int hiRange = findRightIndex(nums, b, 0, length);
        return hiRange - loRange + 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int queryTimes = scanner.nextInt();
        int[] nums = new int[length];
        for (int i = 0; i < length; i++) {
            nums[i] = scanner.nextInt();
        }
        Arrays.sort(nums);

        for (int query = 1; query <= queryTimes; query ++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(range(nums, length, a, b));
        }
    }
}

Java运行结果:

然后改成了我非常不愿意写的C++语言的版本,由此也是发现了C++的强大,做人还是不能偷懒啊。C++虽然难用,指针引用傻傻分不清楚,而且stl在很多情况下会被禁用,但是无奈人家处在底层效率那叫一个高。没有优化的时候就拿了75分,把cin,cout改成scanf,printf之后就能轻松拿满分了。看来这辈子是套不过C++的魔掌了。

stdlib.h中的qsort参见:http://www.cnblogs.com/CCBB/archive/2010/01/15/1648827.html

#include <iostream>
#include <stdlib.h>

using namespace std;

#define L 500005
int nums[L];
/*把常用的变量变成全局的减少参数传递*/

int compare(const void *a, const void *b)
{
    int *pa = (int*)a;
    int *pb = (int*)b;
    return (*pa ) - (*pb);  //从小到大排序
}

int binarySearch1(int target, int lo, int hi) {
    while (lo < hi) {
        // int mid = lo + (hi - lo) / 2;
        int mid = lo + ((hi - lo) >> 1);
        // 若target <= nums[mid],hi = mid,在[lo, mid)中找
        // 若target > nums[mid],lo = mid + 1,在(mid, hi)中
        nums[mid] >= target ? hi = mid : lo = mid + 1;
    }
    return lo; // 循环结束时,lo为>=target的最小下标,故lo-1为<target的最大下标
} // 有多个元素命中target时,保证返回下标最大的;查找失败时返回<target的最大下标

int binarySearch2(int target, int lo, int hi) {
    while (lo < hi) {
        // int mid = lo + (hi - lo) / 2;
        int mid = lo + ((hi - lo) >> 1);
        nums[mid] > target ? hi = mid : lo = mid + 1;
    }
    return --lo; // 循环结束时,lo为>target的最小下标,故lo-1为<=target的最大下标
} // 有多个元素命中target时,保证返回下标最大的;查找失败时返回<=target的最大下标


int range(int length, int a, int b) {
    int loRange = binarySearch1(a, 0, length);
    int hiRange = binarySearch2(b, 0, length);
    return hiRange - loRange + 1;
}

int main() {
    int length, queryTimes;
    scanf("%d %d\n", &length, &queryTimes);
    //cin >> length >> queryTimes;
    //int nums[length];
    for (int i = 0; i < length; i ++) {
        //cin >> nums[i];
        scanf("%d", &nums[i]);
    }

    qsort(nums, length, sizeof(int), compare);

    for (int query = 1; query <= queryTimes; query ++) {
        int a, b;
        //cin >> a >> b;
        scanf("%d %d", &a, &b);
        //cout << range(length, a, b) << endl;
        printf("%d\n", range(length, a, b));
    }
}

一毛一样的算法,但是时间空间都秒杀Java的C++:

最后我要说,我爱C++,C++使我快乐!

results matching ""

    No results matching ""