1 条题解

  • 0
    @ 2026-11-16 20:48:26

    区间定位仪 · 讲解

    思路与接口

    先将所有元素读入 vector<long long>,用 sort 升序排序。排序不会改变各值的出现次数,因此不影响答案。

    对查询 x,lower_bound(begin,end,x) 返回第一个不小于 x 的位置 L,upper_bound(begin,end,x) 返回第一个大于 x 的位置 R。三个半开区间分别为 [begin,L)、[L,R)、[R,end),长度正是小于、等于、大于 x 的数量。使用迭代器相减输出这些长度,不需要访问 L 或 R 指向的元素。

    正确性

    排序后,所有小于 x 的元素位于第一个不小于 x 的位置前,所以其数量为 L−begin。所有等于 x 的元素恰在 L 到 R 之间,数量为 R−L;其后全部大于 x,数量为 end−R。三个区间不相交且覆盖完整序列,重复元素也分别计数。

    n=0 时,begin=end,两个二分搜索都返回 end,三个差值都为 0。当 x 比所有元素大时,L、R 也可能等于 end;迭代器相减仍合法,解引用 end 则不合法。

    复杂度

    排序 O(n log n),每个查询 O(log(n+1)),总时间 O(n log n+q log(n+1)),空间 O(n)。n=0 时每个查询直接得到零计数。

    常见错误

    • 输入顺序任意,却不排序就做二分。
    • 找到一个等于 x 的位置后只计为 1,漏掉其他重复值。配套错误程序展示该错误,大量相同值可拒绝它。
    • 用 lower_bound 同时代替两个边界。
    • 解引用 end() 或不接受 n=0。
    • 忽略边界返回值,导致 x 小于全部元素或大于全部元素时出错。

    数据验证说明

    小规模 oracle 直接逐个比较元素与查询值,大规模使用独立 Python 排序与 bisect。严格输入校验允许空序列但要求至少一个查询,并拒绝包括 n=0 在内的额外 token。

    原创来源记录

    本题题面、样例、代码、讲解与数据从零编写。只使用公开的算法概念和 C++ 标准库接口,没有使用第三方题面、故事、程序或测试文件。

    C++17 参考实现

    #include <algorithm>
    #include <iostream>
    #include <vector>
    using namespace std;
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n, q;
        cin >> n >> q;
        vector<long long> a(n);
        for (auto &value : a) cin >> value;
        sort(a.begin(), a.end());
        while (q--) {
            long long x;
            cin >> x;
            auto left = lower_bound(a.begin(), a.end(), x);
            auto right = upper_bound(a.begin(), a.end(), x);
            cout << left - a.begin() << ' ' << right - left << ' '
                 << a.end() - right << '\n';
        }
    }
    
    
    • 1

    信息

    ID
    5265
    时间
    2000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者