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)表示询问区间。
接下来一行输入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 6Sample 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);
}
}
