题目链接

【模板】整数域二分

题目描述

给定一个长度为 的数组 ，需要处理 次查询：每次给定区间 ，输出数组中满足 的元素个数。

输入：

  • 第一行两个整数 、
  • 第二行 个整数为数组
  • 接下来 行，每行两个整数 、

输出：

  • 对于每次查询，输出一个整数表示区间内元素的个数

解题思路

排序+二分模板：

  • 先将数组 升序排序。
  • 对于每个查询 ，答案为 ：
    • 返回第一个不小于 的位置
    • 返回第一个大于 的位置
  • 二者差即为位于 的元素个数。

该做法是经典的整数域二分应用，预处理一次排序，单次查询二分两次。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    while (q--) {
        long long l, r; cin >> l >> r;
        auto itL = lower_bound(a.begin(), a.end(), l);
        auto itR = upper_bound(a.begin(), a.end(), r);
        cout << (itR - itL) << "\n";
    }
    return 0;
}

import java.util.*;

public class Main {
    static int lowerBound(long[] a, long x) {
        int l = 0, r = a.length; // [l, r)
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a[m] < x) l = m + 1; else r = m;
        }
        return l;
    }
    static int upperBound(long[] a, long x) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a[m] <= x) l = m + 1; else r = m;
        }
        return l;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        Arrays.sort(a);
        while (q-- > 0) {
            long l = sc.nextLong();
            long r = sc.nextLong();
            int ans = upperBound(a, r) - lowerBound(a, l);
            System.out.println(ans);
        }
    }
}

import bisect

n, q = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for _ in range(q):
    l, r = map(int, input().split())
    left = bisect.bisect_left(a, l)
    right = bisect.bisect_right(a, r)
    print(right - left)

算法及复杂度

  • 算法：排序 + 两次二分（lower_bound / upper_bound）
  • 时间复杂度：预处理排序 ，每次查询 ，总计
  • 空间复杂度：（不计输入存储）