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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+5;

int a[N];
int n;

int f(int x){
    int l=0;
    int r=n;
    while(l<r){
        int mid=l+(r-l)/2;
        if(a[mid]>x) r=mid;
        else  l=mid+1;
    }
    return l;
}
int g(int x){
    int l=0;int r=n;
    while(l<r){
        int mid=l+(r-l)/2;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l;
}
int main() {
    int q;cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    while(q--){
        int l,r;cin>>l>>r;
        cout<<f(r)-g(l)<<endl;
    }
}
// 64 位输出请用 printf("%lld")