题目描述
blablabla
样例
blablabla
include[HTML_REMOVED]
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
int n,q;
cin>>n>>q;
for(int i=0;i[HTML_REMOVED]>a[i];
while(q–){
int k;
cin>>k;
int l=0,r=n-1;
while(l[HTML_REMOVED]=k) r=mid;
else l=mid+1;
}
if(a[l]!=k) cout<<”-1 -1”<<endl;
else{
cout<<l<<” “;
int l=0,r=n-1;
while(l<r){
int mid=(l+r+1)/2;
if(a[mid]<=k) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
}
}
此题求该数的起始位置和末位置,可以这样帮助理解 有关mid 的众多操作:
while(l<r){
int mid=l+r>>1; //起点比终点更左,所以区域划分为l~mid
if(a[mid]>=x) r=mid; //则必为r=mid,反推a[mid]>=x
else l=mid+1; //再推出mid=l+r>>1
}
while(l<r){
int mid=l+r+1>>1; //终点比起点更右,所以区域划分为mid~r
if(a[mid]<=x) l=mid; //则必为l=mid,反推a[mid]<=x
else r=mid-1; //再推出mid=l+r+1>>1
}
blablabla