jdoj 1849 范围统计

题目传送门

Description

给出n个整数Xi和m个询问,对于每个询问(a,b),输出闭区间[a,b]内的整数xi的个数。

Input

输入第一行输入两个正整数n(1<=n<=105)和m(1<=m<=105)
接下来一行输入n个正整数分别为X1,X2,...,Xn(1<=Xi<=109)。
接下来m行,每行两个整数Ai,Bi(1<=Ai<=Bi<=109)表示询问区间。

Output

对于每个询问,输出[Ai,Bi]内的整数Xi的个数。

Sample Input

3 2
1 3 5
2 4
1 6

Sample Output

1
3

思路:

这道题乍一看并没有什么思路 好,我们先来想暴力,暴力方法就不多说了,第一时间想到的暴力一定是O(n^2)的暴力。然后,我们想如何优化:我们可不可以将数据排一个序?从左右端点开始枚举,遇到第一个大于等于左边界的数就停,同理,遇到第一个小于等于右边界的数就停,这样暴力的方法似乎更优?等等,这个方法花费的绝大部分时间都在查找,那么,我们就可以二分啊,时间复杂度骤降至O(mlogn)

这道题还是很锻炼二分姿势的......我也不知道我写的是不是对的......应该会被极限数据卡的吧...... 然而我过了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int a[110000];
int find(int z)
{
    int x=0,y=n;
    int mid=(x+y)>>1;
    while(x<y)
    {
        if(a[mid]>z) y=mid;
        else if(a[mid]<z) x=mid+1;
        else return mid;
        mid=(x+y)>>1;
    }
    return x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    a[++n]=0x7f7f7f7f;
    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++)
    {
        int dx,dy;
        scanf("%d%d",&dx,&dy);
        int dxx=find(dx-1),dyy=find(dy+1);
        while(a[dxx]<dx)dxx++;
        while(a[dyy]>dy)dyy--;
        printf("%d\n",dyy-dxx+1);
    }
}

 

发表评论

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