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

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int a[N];
int n, q;
int leftBound(int x);
int rightBound(int x);

int main() {
    cin >> n >> q;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    sort(a, a + n);

    int l, r;
    for(int i = 0; i < q; ++i){
        cin >> l >> r;
        cout << rightBound(r) - leftBound(l) + 1 << endl;
    }
}

int leftBound(int x){   //查找第一个大于等于x的位置
    int l = -1, r = n - 1;
    while(l + 1 != r){
        int mid = l + (r - l) / 2;
        if(a[mid] >= x) r = mid;
        else l = mid;
    }
    return r;
}

int rightBound(int x){   //查找最后一个小于等于x的位置
    int l = 0, r = n;
    while(l + 1 != r){
        int mid = l + (r - l) / 2;
        if(a[mid] <= x) l = mid;
        else r = mid;
    }
    return l;
}