AcWing 789. 数的范围
原题链接
简单
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 1e6+10;
int arr[MAXN];
int N,M;
int main(){
scanf("%d%d",&N,&M);
for(int i = 0; i < N; i++){
scanf("%d",&arr[i]);
}
for(int i = 0; i < M; i++){
int a;
int start = -1,end = -1;
scanf("%d",&a);
//求upper_bound
int l = 0, r = N-1;
while(l < r){
int mid = l+r+1>>1;
if(arr[mid] <= a) l = mid;
else r = mid-1;
}
if(arr[l] == a) start = l;
//求lower_bound
l = 0, r = N-1;
while(l < r){
int mid = l+r>>1;
if(arr[mid] >= a) r = mid;
else l = mid+1;
}
if(arr[l] == a) end = l;
printf("%d %d\n",end,start);
}
return 0;
}