喵~ 各位算法爱好者们，大家好呀！今天，本喵要和大家一起探讨一道非常经典的问题——Codeforces 600B: Queries about less or equal elements。这道题对于新手来说，是学习和理解二分查找的绝佳练习哦。那么，就让我们一起开始吧！

题目大意

这道题的描述非常简单直接，喵~

我们有两个整数数组，分别叫做 a 和 b。对于数组 b 中的每一个元素 b[j]，我们需要找出数组 a 中有多少个元素是小于或等于 b[j] 的。

举个例子吧，一看就懂啦！ 假设数组 a 是 {1, 3, 5, 7, 9}，数组 b 是 {6, 4, 2, 8}。

• 对于 b 的第一个元素 6，a 中小于等于 6 的有 {1, 3, 5}，一共 3 个。
• 对于 b 的第二个元素 4，a 中小于等于 4 的有 {1, 3}，一共 2 个。
• 对于 b 的第三个元素 2，a 中小于等于 2 的有 {1}，一共 1 个。
• 对于 b 的第四个元素 8，a 中小于等于 8 的有 {1, 3, 5, 7}，一共 4 个。

所以，最后的输出就是 3 2 1 4，是不是很简单呢？喵~

题解方法

朴素的想法（会超时的哦~）

最直接的想法是什么呢？当然是暴力枚举啦！对于 b 数组中的每一个数，我们都去遍历一遍 a 数组，一个一个地比较，然后用一个计数器记录下符合条件的元素个数。

这个方法虽然简单，但是效率太低了呀。题目中 n 和 m 的最大值都可以达到 2 * 10^5。如果用暴力法，时间复杂度会是 O(n * m)，算下来就是 (2 * 10^5) * (2 * 10^5) = 4 * 10^10 次运算，这会让计算机累坏的，肯定会超时的喵！所以，我们得想个更聪明的办法。

优化的思路（排序 + 二分查找）

当我们需要在一个庞大的数据集中快速查找时，应该立刻想到什么呢？对啦！就是二分查找！

但是，二分查找有一个前提条件：数据必须是有序的。我们的 a 数组一开始是无序的，所以第一步，我们应该先把它排个序。

排序之后，数组 a 就变成了一个单调递增的序列。这时候，对于任意一个查询值 b[j]，所有小于等于 b[j] 的元素肯定都集中在数组 a 的最左边，形成一个连续的区间。

我们的问题就转化成了：在排好序的数组 a 中，找到第一个大于 b[j] 的元素的位置。这个位置的下标，恰好就是 a 中小于等于 b[j] 的元素个数！

比如说，排序后的 a 是 {1, 3, 5, 7, 9}。我们要找小于等于 6 的元素个数。 我们在 a 中找到第一个大于 6 的数，是 7。7 的下标是 3 (从0开始数)。于是，答案就是 3。是不是很神奇？喵~

而这个“查找第一个大于某个值的元素”的操作，C++ 的标准库 STL 已经为我们准备好了，它就是 std::upper_bound 函数。它使用二分查找，效率非常高，时间复杂度是 O(log n)。

所以，我们的最终方案就是：

1. 对数组 a 进行排序。 (时间复杂度 O(n log n))
2. 对于数组 b 中的每个元素 b[j]，使用 std::upper_bound 在 a 中查找。 (每次查询 O(log n)，共 m 次)

总时间复杂度就是 O(n log n + m log n)，这个效率就非常高啦，完全可以通过本题！

题解代码 (C++)

这是本喵为大家准备的参考代码，加了一些注释方便理解哦~

#include <iostream>
#include <vector>
#include <algorithm>

// 将核心逻辑封装在 solve 函数里，是个好习惯喵~
void solve() {
    int n, m;
    // 读取数组 a 和 b 的大小
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 第一步：先把 a 数组排个序，喵~
    // 排序的时间复杂度是 O(n log n)
    std::sort(a.begin(), a.end());

    // 第二步：处理 m 次查询
    for (int i = 0; i < m; ++i) {
        int b_val;
        std::cin >> b_val;

        // 使用 std::upper_bound 进行二分查找
        // 它会找到第一个 *严格大于* b_val 的元素的位置（迭代器）
        // 这个操作的时间复杂度是 O(log n)
        auto it = std::upper_bound(a.begin(), a.end(), b_val);

        // 这个迭代器减去数组的起始迭代器，得到的就是它前面元素的个数
        // 这也正好是小于等于 b_val 的元素数量
        int count = it - a.begin();

        // 输出当前查询的结果
        std::cout << count;

        // 除了最后一个结果，其他结果后面都要加个空格哦
        if (i < m - 1) {
            std::cout << " ";
        }
    }
    // 所有输出结束后，换个行
    std::cout << std::endl;
}

int main() {
    // 这两行是用于加速 C++ 的输入输出的，在打比赛时很有用哦
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

相关知识点介绍

1. 二分查找 (Binary Search)

二分查找是一种在有序数组中查找某一特定元素的搜索算法。它的工作原理是：

1. 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束。
2. 如果目标值大于中间元素，则在数组大于中间元素的那一半中查找。
3. 如果目标值小于中间元素，则在数组小于中间元素的那一半中查找。
4. 重复以上过程，直到找到目标值，或者待搜索的区间为空。

因为每次都把搜索范围缩小一半，所以它的查找速度非常快，时间复杂度是 O(log n)。

2. std::lower_bound 和 std::upper_bound

这两个是 C++ STL 中非常有用的函数，它们都基于二分查找，并且要求操作的区间是已排序的。

• std::lower_bound(first, last, val):

  • 返回一个迭代器，指向区间 [first, last) 中第一个不小于（也就是大于或等于 ≥）val 的元素。
  • 如果所有元素都小于 val，则返回 last。

• std::upper_bound(first, last, val):

  • 返回一个迭代器，指向区间 [first, last) 中第一个严格大于 > val 的元素。
  • 如果所有元素都小于或等于 val，则返回 last。

利用这两个函数，我们可以高效地计算区间内满足特定条件的元素数量：

• 计算小于 val 的元素个数: std::lower_bound(a.begin(), a.end(), val) - a.begin()
• 计算小于等于 val 的元素个数: std::upper_bound(a.begin(), a.end(), val) - a.begin() (正是本题的解法！)
• 计算等于 val 的元素个数: std::upper_bound(...) - std::lower_bound(...)

希望这次的讲解对大家有帮助！如果还有不明白的地方，可以多看看代码和知识点介绍哦。下次再见啦，喵~！