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

#include <bits/stdc++.h>
using ll  = long long;
using namespace std;
 ll n,q;
const int N = 2e5+5;
vector<ll>a(N,0);
ll solve1(ll x)//找第一个大于等于l的数
{
    ll mid ;
    ll l =  1;
    ll r = n;
    while(l<r)
    {
        mid = (l+r)>>1;
        if(a[mid]>=x) r = mid;//尽量往左找
        else l = mid + 1;
    }
    return l;
}
ll solve2(ll x)//找最后一个一个小于等于r的数
{
    ll mid ;
    ll l =  1;
    ll r = n;
    while(l<r)
    {
        mid = (l+r+1)>>1;//尽量往右找
        if(a[mid]<=x) l = mid;
        else r = mid - 1;
    }
    return l;
}
 
int main()
{
    cin>>n>>q;
    for(ll i = 1;i <= n;i++)cin>>a[i];
    sort(a.begin()+1,a.begin()+n+1);
    while(q--)
    {
        ll l,r;
        cin>>l>>r;
        cout<<solve2(r)-solve1(l)+1<<endl;
    }
    return 0;
}