把每个值映射到它出现的下标有序数组,一次询问只需两次二分。
(GESP 样题 · 八级)小杨有一个长度为 n 的正整数序列 A。小杨有 q 次询问。第 i 次(1 ≤ i ≤ q)询问时,小杨会给出 lᵢ, rᵢ, xᵢ,请你求出 xᵢ 在 A_{lᵢ}, A_{lᵢ+1}, … A_{rᵢ} 中出现的次数。
输入格式:第一行包含一个正整数 T,表示数据组数。
对于每组数据:第一行包含一个正整数 n,表示序列 A 的长度;第二行包含 n 个正整数 A₁, A₂, … , Aₙ,表示序列 A;第三行包含一个正整数 q,表示询问次数;接下来 q 行,每行三个正整数 lᵢ, rᵢ, xᵢ,表示一组询问。
输出格式:对于每组数据,输出 q 行。第 i 行(1 ≤ i ≤ q)输出一个非负整数,表示第 i 次询问的答案。
子任务:
| 子任务 | 分值 | n | q | max Aᵢ |
|---|---|---|---|---|
| 1 | 30 | ≤ 100 | ≤ 100 | ≤ 10 |
| 2 | 30 | ≤ 10⁵ | ≤ 10⁵ | ≤ 10⁵ |
| 3 | 40 | ≤ 10⁵ | ≤ 10⁵ | ≤ 10⁹ |
对于全部数据,保证 1 ≤ T ≤ 5,1 ≤ n, q ≤ 10⁵,1 ≤ Aᵢ ≤ 10⁹。
A,然后反复被问"第 l 个到第 r 个之间,数字 x 出现了几次"。A_l … A_r 扫一遍数一数。单次 O(n),q 次就是 O(nq) = 10¹⁰ 级别,必超时。[l, r] 里的个数 = [1, r] 里的个数 − [1, l−1] 里的个数。x,把它出现的所有位置排成一个有序数组 P,问 x 时就在 P 上二分两次:upperBound(P, r) − lowerBound(P, l)。O(log n),总复杂度 O((n + q) log n),稳过。区间内计数值 → 出现位置列表lower_bound / upper_bound值域 10⁹ 开不了桶二分查找
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 T;每组数据:n → 序列 A → q → q 行 (l, r, x) |
| 输出 | 每组数据输出 q 行,每行一个非负整数 |
| 数据范围 | 1 ≤ T ≤ 5,1 ≤ n, q ≤ 10⁵ |
| 数值范围 | 1 ≤ Aᵢ ≤ 10⁹(值域很大) |
| 询问含义 | 统计 A_l, A_{l+1}, … , A_r 中等于 x 的元素个数 |
| 时限 | 1000 ms / 256 MB(开 10⁹ 大小的数组必爆) |
max Aᵢ ≤ 10⁵,开 10⁵ 个桶确实可行;但子任务 3 的 Aᵢ 可以到 10⁹,10⁹ 个 int 就是 4 GB 内存,直接爆掉,所以"值域数组"这条路走不通n 个。用映射把值接到它的出现位置列表上,所有列表的元素总数恰好是 n,与值域大小完全无关x 的位置列表为 P(因为从左到右扫描,天然递增)。那么"P 中不大于 r 的个数"是 upper_bound(P, r),"P 中小于 l 的个数"是 lower_bound(P, l),两者相减就是落在 [l, r] 里的个数x 从没出现过怎么办?在映射里查不到 x,直接输出 0,千万不要去访问一个不存在的列表(否则会越界 / 报错)样例输入是这样两组数据(第一组有环状重复,第二组是递增序列):
2 5 7 4 6 1 1 2 1 2 3 1 5 1 5 1 2 3 4 5 2 5 5 3 1 4 3
期望输出是 0 / 2 / 0 / 1,我们把它一条条算出来。
| 值 | 出现的下标列表 P |
|---|---|
| 7 | [1] |
| 4 | [2] |
| 6 | [3] |
| 1 | [4, 5] |
| 询问 | P(x 的下标列表) | upper_bound(P, r) | lower_bound(P, l) | 答案 |
|---|---|---|---|---|
| (1, 2, 3) | 3 没出现过 → 无此 key | — | — | 0 |
| (1, 5, 1) | [4, 5] | 2(≤ 5 的有 4、5) | 0(< 1 的有 0 个) | 2 |
| 值 | 出现的下标列表 P |
|---|---|
| 1 | [1] |
| 2 | [2] |
| 3 | [3] |
| 4 | [4] |
| 5 | [5] |
| 询问 | P(x 的下标列表) | upper_bound(P, r) | lower_bound(P, l) | 答案 |
|---|---|---|---|---|
| (5, 5, 3) | [3] | 1(≤ 5 的有 3) | 1(< 5 的有 3) | 0 |
| (1, 4, 3) | [3] | 1(≤ 4 的有 3) | 0(< 1 的有 0 个) | 1 |
输出 0 / 2 / 0 / 1 ✓
P = [3],问 [5, 5]:
upper_bound(P, 5) = 1,说明"≤ 5"的只有 1 个(下标 3)
lower_bound(P, 5) = 1,说明"< 5"的也是 1 个(下标 3 < 5)
相减 1 − 1 = 0:下标 3 落在 5 之前,不在 [5, 5] 里
✅ 答案 0
P = [3],问 [1, 4]:
upper_bound(P, 4) = 1(下标 3 ≤ 4)
lower_bound(P, 1) = 0(没有下标 < 1)
相减 1 − 0 = 1
✅ 答案 1
若问 (1, 5, 99):映射里根本没有 99 这个 key,
此时必须特判输出 0,
不能拿着空列表去二分(虽然空列表也能返回 0,
但用 map 时 find 不到会直接拿到空对象,容易被判错)
✅ 答案 0
[l, r] 内的个数 = "≤ r 的个数" − "< l 的个数"。P 上二分得到,分别对应 upper_bound(P, r) 与 lower_bound(P, l)。把两条路线摆在一起看,差距一眼就出来了:
| 路线 | 需要的空间 | 单次询问 | 能否处理 Aᵢ ≤ 10⁹ |
|---|---|---|---|
| 值域桶 + 逐值前缀和 | O(max A × n) 或至少 O(max A) | O(1) | ❌ 开不下 10⁹ 个桶 |
| 值 → 出现下标列表 + 二分 | O(n) | O(log n) | ✅ 完全不受值域影响 |
因为 max Aᵢ ≤ 10⁵,可以开 cnt[值][位置] 或
"对每个值维护一个前缀和数组"
甚至能 O(1) 回答一次询问
但它把"值域"当成了必须支付的成本
⚠️ 只对子任务 2 有效
max Aᵢ 跳到 10⁹,任何"按值域开数组"的方案都要 10⁹ 级别空间
但序列只有 n ≤ 10⁵ 个数
也就是"值域稀疏、取值都挤在很小的一个子集里"
于是用映射把值离散化,只保留出现过的值
✅ 下标列表 + 二分
建表扫描一遍 O(n)
每次询问两次二分 O(log n)
总共 O((n + q) log n)
T ≤ 5 时最坏约 5 × (10⁵ × 17 + 2 × 10⁵ × 17) ≈ 2.5 × 10⁷ 次操作
✅ 1000 ms 内轻松跑完
x 不在序列中",写成了 pos[x] 却得到一个空的 / 越界的容器;② 二分对象搞混:求 "≤ r" 必须用 upper_bound(找第一个 > r 的位置),求 "< l" 必须用 lower_bound(找第一个 ≥ l 的位置),两个函数写法只差一个字符,用错答案就整体偏 1。读入时为每个值记录它出现的下标(天然递增);询问时在对应列表上二分
n,再大的值域也只需要 O(n) 的空间。开一个大小等于值域上界的桶数组,按值做前缀和
O(max A) 或更多max A ≤ 10⁵ 时可行max A ≤ 10⁹ 时直接爆内存10⁹ 个桶就是约 4 GB,这不是"慢一点"而是"根本开不出来"。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 下标列表 + 二分 | O((n + q) log n) / O(n) | ✅ 全子任务通吃 |
| 值域桶 + 前缀和 | O(1) 询问 / O(max A) 空间 | ⚠️ 只有 60 分(值域小时才行) |
| 每次询问暴力扫描 | O(nq) = 10¹⁰ | ❌ 必超时 |
第一行输入 n 与 q,第二行输入 n 个整数(序列 A),接下来 q 行每行 l r x。程序用"值 → 下标列表 + 二分"逐条回答。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); // 值 -> 它出现的所有下标(从左往右扫描,列表天然递增) map<int, vector<int> > pos; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); pos[x].push_back(i); } int q; scanf("%d", &q); while (q--) { int l, r, x; scanf("%d %d %d", &l, &r, &x); map<int, vector<int> >::iterator it = pos.find(x); if (it == pos.end()) { // x 从未出现,答案直接是 0 printf("0\n"); continue; } const vector<int>& P = it->second; // 落在 [l, r] 内的个数 = "<= r 的个数" - "< l 的个数" int hi = upper_bound(P.begin(), P.end(), r) - P.begin(); int lo = lower_bound(P.begin(), P.end(), l) - P.begin(); printf("%d\n", hi - lo); } } return 0; }
upper_bound(P, r) − lower_bound(P, l)。upper_bound 找第一个 > r 的位置,所以它就是"≤ r 的元素个数";lower_bound 找第一个 ≥ l 的位置,所以它就是"< l 的元素个数"。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
map<int, vector<int> > pos; | 值 → 下标列表的索引 | 值域 10⁹ 也能存,等价于对值做离散化 |
pos[x].push_back(i); | 按原始位置登记 | i 从 1 开始,逐位递增,列表天然有序 |
if (it == pos.end()) ... | 特判 x 不存在 | 该 query 的答案一定是 0,别去碰空容器 |
upper_bound(P.begin(), P.end(), r) | 数出 ≤ r 的个数 | 返回的是迭代器,减 P.begin() 得到个数 |
lower_bound(P.begin(), P.end(), l) | 数出 < l 的个数 | 与上一行相减,恰好是区间 [l, r] 内的个数 |
upper_bound 和 lower_bound 用反(答案整体偏移);② 忘记"x 不存在"的特判;③ 下标从 0 开始存,却拿 1 起的 l, r 去比;④ 多组数据没有清空 pos(每轮重新声明即可)。map 常数大,可以把所有 (Aᵢ, i) 排序后二分找 x 的整段区间,逻辑一样,只是"索引"换成了排序 + 二分。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 | 0 2 0 1 | 题面样例:两组数据共 4 行输出 |
1 | 1 0 1 | 单点命中 / x 完全不在序列里 / 整段计数 |
1 | 3 1 | 值域到 10⁹:只有下标列表方案能过(开桶必爆) |
1 | 2 2 3 | 区间截断:注意 [2, 5] 两端的下标归属 |
1 | 4 0 | 全相同序列 / 查询一个根本不存在的值 |
x 不存在时输出 0 了吗?③ 是 upper_bound(P, r) − lower_bound(P, l) 吗?④ 多组数据之间清空了吗?0,新手常写成 pos[x].size(),容器不存在就出错。upper_bound、"< l" 用 lower_bound,写反会让答案整体偏 1。l, r 同步换算。T 组之间索引结构必须重来一遍,否则上一组的值会污染这一组。n 个元素,用平衡树索引是 O(n log n)(用哈希表则 O(n))O(log n)O((n + q) log n),最坏 T = 5、n = q = 10⁵ 时约 2.5 × 10⁷ 次操作映射本身存 n 个键值对;所有下标列表的元素总数恰好是 n(每个位置只属于一个列表),再加上几个常数数组,空间是 O(n)。
✅ 与值域无关的 O(n) 空间,配合 O(log n) 的询问,是这道题唯一能通吃 40 分子任务的做法。
// 「值 -> 出现位置列表」+ 二分 的通用模板 vector<int> pos[MAXV]; // 值域小时直接开数组 // map<int, vector<int> > pos; // 值域大时用平衡树索引 // unordered_map<int, vector<int> > pos; // 追求常数时用哈希表 for (int i = 1; i <= n; i++) pos[a[i]].push_back(i); // 下标天然递增 // ---- 询问:区间 [l, r] 中 x 的个数 ---- int cnt = upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l); // ---- 变体 1:区间 [l, r] 中"第一个 >= x 的位置" ---- // lower_bound 在合并后的有序集合上做(或对每个值二分后取最小) // ---- 变体 2:x 的第 k 次出现的位置 ---- // pos[x].size() < k -> 不存在;否则 pos[x][k - 1]
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 值 → 出现位置列表 | 把稀疏的值域压成 O(n) 的空间 | "值域大但取值稀疏"的一切计数题 |
| 前缀之差降区间 | 区间计数 = 两个前缀计数相减 | 区间和、区间异或、区间 gcd 等一切可减信息 |
| 两次二分定位 | upper_bound 数 ≤ r、lower_bound 数 < l | 统计落在区间内的元素个数、求第 k 个不小于某值的元素 |
| 离线离散化 | 只保留"出现过的值"作为 key | 坐标压缩、值域过大时的所有索引结构 |
A_l … A_r 中一共有多少个不同的值",这套"值 → 位置列表"还够用吗?(提示:不够直接套,但可以沿着另一条思路走——对每个位置 i 记录"上一个与 Aᵢ 相同的下标 pre[i]",那么"不同值的个数"就等于统计 i ∈ [l, r] 中 pre[i] < l 的个数,这又变成了一个离线 + 树状数组的经典问题。把"值 → 位置"换成"位置 → 上一个同值位置",是这套离散化思想的常见升级方向。)