1 条题解
-
0
区间定位仪 · 讲解
思路与接口
先将所有元素读入
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
- 上传者