题解

题意
给定长度为 $n$ 的整数序列，之后有 $q$ 次询问。每次给出一个数字 $x$，求出序列中 $x$ 出现多少次。

---

思路
$1.$ 将数组从小到大排序。
$2.$ 二分查找两个位置：
$\quad$$\circ$ bs_left(x)：第一个大于等于 $x$ 的下标（左边界）
$\quad$$\circ$ bs_right(x)：最后一个小于等于 $x$ 的下标（右边界）
$4.$ 如果找不到 $x$，答案为 $0$；
$\quad$否则 数量 = 右边界 $-$ 左边界 $+ 1$。

---

完整代码

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

const int N = 1e6 + 5;
int n,q;
int a[N];
int bs_left(int x) {
    int l = 0, r = n + 1, mid;
    while (l+1 < r) {
        mid = (l + r) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid;
    }
    if (r == n + 1 || a[r] != x) return -1;
    return r;
}

int bs_right(int x) {
    int l = 0, r = n + 1, mid;
    while (l+1 < r) {
        mid = (l + r) / 2;
        if (a[mid] > x) r = mid;
        else l = mid;
    }
    if (l == 0 || a[l] != x) return -1;
    return l;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+1+n);
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int u = bs_left(x), v = bs_right(x);
        if (u == -1 || v == -1) cout << 0 << '\n';
        else cout << v - u + 1 << '\n';
    }
    return 0;
}