题解 | 【模板】整数域二分

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;

int n,q,x,y;
int a[N]; 

void solve(){
	
	int res1,res2;
	
	int l=1,r=n,mid;
	while(l<=r){
		mid=l+r>>1;
		if(a[mid]>x){
			r=mid-1;
			res1=mid;
		}else if(a[mid]<x){
			l=mid+1;
		}else if(a[mid]==x){
			r=mid-1;
			res1=mid;
		}
	}
	
	l=1,r=n;
	while(l<=r){
		mid=l+r>>1;
		if(a[mid]>y){
			r=mid-1;
		}else if(a[mid]<y){
			l=mid+1;
			res2=mid;
		}else if(a[mid]==y){
			l=mid+1;
			res2=mid;
		}
	}
	
	cout<<res2-res1+1<<endl;
	
//	cout<<res<<endl;
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		solve();
	}
	

    return 0;
}