长征路上的学习之旅 题解

题目分析

本题的核心问题可以概括为：给定一系列坐标点（革命纪念馆和烈士陵园），需要多次回答区间查询：在某个坐标范围 $[x - R, x + R]$ 内，共有多少个点。

虽然输入分成了两类建筑，但关心的是所有建筑的总数，因此两类建筑可以合并处理，无需区分。于是问题转化为经典的区间计数问题。

解题思路

对于每一次询问，直接遍历所有的点去统计是会超时的。因为 $A+B$ 与 $Q$ 都可能很大（题目未明确上限，但从时间限制和参考代码可推断数据规模较大），我们需要一种高效的方法。

高效处理大量区间查询的常用技巧是排序 + 二分查找：

• 将所有建筑的坐标存入一个数组，并排序。
• 对于每次询问的区间 $[L, R]$ （其中 $L = x - R, R = x + R$），我们需要知道数组中大于等于 $L$ 且小于等于 $R$ 的元素有多少个。
• 在有序数组中，可以利用 lower_bound 找到第一个 $\ge L$ 的位置，用 upper_bound 找到第一个 $>R$ 的位置（即小于等于 $R$ 的最后一个位置的下一个位置）。两个迭代器（指针）的差值就是落在区间内的元素个数。

这样，每次询问只需要两次二分查找，时间复杂度为 $O(\log N)$，其中 $N = A + B$。

算法说明

1. 合并数据
   将所有的纪念馆坐标和陵园坐标读入同一个数组 buildings 中。

2. 排序
   对 buildings 数组从小到大排序，这是二分查找的前提。

3. 处理询问
   对于每个询问 $(x, R)$：

   • 计算左边界 left_bound = x - R，右边界 right_bound = x + R。
   • 使用 lower_bound 在数组中查找第一个不小于 left_bound 的元素位置，记为 it_left。
   • 使用 upper_bound 在数组中查找第一个大于 right_bound 的元素位置，记为 it_right。
   • 区间内建筑的数量 = it_right - it_left。

4. 输出结果
   每个询问输出一行答案。

时间复杂度分析

• 合并与排序：设 $N = A + B$，排序的时间复杂度为 $O(N \log N)$。
• 每次询问：两次二分查找，每次 $O(\log N)$，$Q$ 次询问总复杂度为 $O(Q \log N)$。
• 总体复杂度：$O(N \log N + Q \log N)$，在一般数据范围下都能高效运行。

细节与易错点

• 数据范围：坐标和半径可能达到 $10^{10}$，必须使用 long long 类型存储，避免溢出。
• 输入效率：可使用 ios_base::sync_with_stdio(false); cin.tie(NULL); 加速输入，避免超时。
• 边界条件：lower_bound 与 upper_bound 的组合正好能够准确统计闭区间内的元素个数，无需做额外的偏移处理。

参考代码

cpp
复制
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int main() {
8    // 优化输入输出效率
9    ios_base::sync_with_stdio(false);
10    cin.tie(NULL);
11
12    int A, B, Q;
13    cin >> A >> B >> Q;
14
15    // 使用 vector 存储所有建筑的坐标（总数量为 A + B）
16    vector<long long> buildings(A + B);
17
18    // 读入 A 个纪念馆坐标
19    for (int i = 0; i < A; ++i) {
20        cin >> buildings[i];
21    }
22
23    // 读入 B 个陵园坐标，接在纪念馆后面
24    for (int i = 0; i < B; ++i) {
25        cin >> buildings[A + i];
26    }
27
28    // 对所有坐标进行排序，以便进行二分查找
29    sort(buildings.begin(), buildings.end());
30
31    // 处理 Q 次询问
32    while (Q--) {
33        long long x, r;
34        cin >> x >> r;
35
36        // 计算探索范围的左右边界
37        long long left_bound = x - r;
38        long long right_bound = x + r;
39
40        // 使用 lower_bound 找到第一个 >= left_bound 的位置
41        auto it_left = lower_bound(buildings.begin(), buildings.end(), left_bound);
42
43        // 使用 upper_bound 找到第一个 > right_bound 的位置
44        auto it_right = upper_bound(buildings.begin(), buildings.end(), right_bound);
45
46        // 两个迭代器之间的距离就是区间内的元素个数
47        long long count = it_right - it_left;
48
49        cout << count << "\n";
50    }
51
52    return 0;
53}

代码解释

• vector<long long> buildings(A + B);：动态数组，容量为两类建筑数量之和。
• sort(...)：默认升序排序。
• lower_bound(begin, end, val)：返回指向第一个 $\ge val$ 的元素的迭代器，若不存在则返回 end。
• upper_bound(begin, end, val)：返回指向第一个 $>val$ 的元素的迭代器。
• 两个迭代器相减得到区间内元素个数，结果为整数类型（ptrdiff_t 可隐式转换为 long long）。

总结

这道题考察了将实际问题抽象为区间查询的能力，以及利用排序 + 二分查找优化查询的经典方法。对初学者而言，理解 lower_bound 和 upper_bound 的用法非常重要，它们是竞赛中处理有序数组查询的利器。