如何用lower_bound与upper_bound优化多区间数字匹配算法？

你的思路完全正确——用lower_bound和upper_bound确实能把时间复杂度从O(nm)优化到O((n+m)logn)，咱们一步步拆解怎么改造你的代码：

核心优化思路 #

暴力解法里，每个区间都要遍历所有n个数字，当n和m都是十万级别的时候肯定会超时。优化的关键是先把数字数组排序，然后对每个区间用二分法快速定位符合条件的数字范围，这样每个区间的查询只需要O(logn)的时间，整体效率会提升一大截。

关键函数快速理解 #

先给你理清楚这两个二分查找函数的作用（它们要求容器是有序的，这是前提）：

• lower_bound(begin, end, val)：返回容器中第一个大于等于val的元素的迭代器。
• upper_bound(begin, end, val)：返回容器中第一个大于val的元素的迭代器。

对于区间[L, R]，我们要找所有满足L ≤ x ≤ R的数字：用lower_bound找到第一个≥L的位置，用upper_bound找到第一个>R的位置，这两个迭代器之间的元素个数就是符合条件的数字数量——因为vector的迭代器是随机访问迭代器，直接相减就能得到元素个数，和数组下标相减是一个道理。

修改后的完整代码 #

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

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    
    int n, m, temp, temp1;
    vector<int> erskeciai;
    vector<pair<int, int>> uogienes;
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        erskeciai.push_back(temp);
    }
    
    // 关键步骤：先对数字数组排序，二分查找的前提
    sort(erskeciai.begin(), erskeciai.end());
    
    for (int i = 0; i < m; i++) {
        cin >> temp >> temp1;
        uogienes.push_back(make_pair(temp, temp1));
    }
    
    for (auto &interval : uogienes) {
        int L = interval.first;
        int R = interval.second;
        
        // 找到第一个 >= L 的元素迭代器
        auto left = lower_bound(erskeciai.begin(), erskeciai.end(), L);
        // 找到第一个 > R 的元素迭代器
        auto right = upper_bound(erskeciai.begin(), erskeciai.end(), R);
        
        // 两个迭代器的差值就是区间内的数字数量
        cout << (right - left) << "\n";
    }
    
    return 0;
}

代码关键点说明 #

1. 排序数组：sort(erskeciai.begin(), erskeciai.end())是整个优化的基础，没有有序数组，二分查找函数无法工作，这一步的时间复杂度是O(nlogn)。
2. 迭代器的使用：用auto自动推导迭代器类型，不用手动写vector<int>::iterator，代码更简洁。right - left直接得到元素个数，这是随机访问迭代器的特性。
3. 输入输出优化：你原来的cin.tie(0)等代码保留得很好，继续用可以大幅加快输入输出速度，避免大数据量下的超时。

时间复杂度验证 #

• 排序阶段：O(nlogn)
• m个区间的查询阶段：每个查询O(logn)，总时间O(mlogn)
• 整体时间复杂度：O(nlogn + mlogn) = O((n+m)logn)，比暴力的O(nm)高效太多，尤其适合大数据量场景。

内容的提问来源于stack exchange，提问作者J. Doe