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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;

ll a[N];  // 存储数组元素
ll L, R;  // 每次查询的区间左右边界

// 二分条件1：判断a[m]是否小于L（用于找第一个>=L的位置）
bool isl_1(ll m) {
    if (a[m] < L) {
        return true;
    } else return false;
}


// 二分条件2：判断a[m]是否小于等于R（用于找最后一个<=R的位置）
bool isl_2(ll m) {
    if (a[m] <= R) {
        return true;
    } else return false;
}

int main() {
    // 加速输入输出
    cin.tie(0)->sync_with_stdio(0);
    ll n, q;
    cin >> n >> q; // 读入数组长度n和查询次数q

    // 读入数组元素
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 核心步骤1：对数组排序（为后续二分查找做准备）
    sort(a + 1, a + n + 1);

    // 处理q次查询
    while (q--) {
        cin >> L >> R; // 读入当前查询的区间[L, R]

        // ---------------------------
        // 二分1：找第一个 >= L 的元素的位置
        // 初始区间是[0, n+1]（数组下标是1~n，0和n+1是边界哨兵）
        // ---------------------------
        ll l = 0, r = n + 1;
        // 二分循环：当左右指针未相邻时继续
        while (l + 1 != r) {
            ll m = (l + r) / 2; // 取中间位置
            if (isl_1(m)) { // 若a[m]<L，说明目标位置在m右侧
                l = m;
            } else {        // 否则目标位置在m左侧
                r = m;
            }
        }
        ll res1 = l; // 循环结束后，res1是最后一个小于L的位置（即第一个>=L的位置是res1+1）

        // ---------------------------
        // 二分2：找最后一个 <= R 的元素的位置
        // 初始区间同样是[0, n+1]
        // ---------------------------
        l = 0;
        r = n + 1;
        while (l + 1 != r) {
            ll m = (l + r) / 2; // 取中间位置
            if (isl_2(m)) { // 若a[m]<=R，说明目标位置在m右侧
                l = m;
            } else {        // 否则目标位置在m左侧
                r = m;
            }
        }
        ll res2 = l; // 循环结束后，res2是最后一个<=R的位置

        // ---------------------------
        // 结果计算：区间[L,R]的元素个数 = 最后一个<=R的位置 - 最后一个<L的位置
        // ---------------------------
        cout << res2 - res1 << endl;
    }
    return 0;
}