GESP 题解库 / 8 级题解 / [GESP样题 八级] 区间 · 第 22 / 24 题
GESP样题 八级 · P10288 · 中等

区间出现次数

把每个值映射到它出现的下标有序数组,一次询问只需两次二分。

📏
n, q ≤ 10⁵
序列长度 / 询问次数
🔢
Aᵢ ≤ 10⁹
值域太大,开不了桶
⚡
O((n + q) log n)
建表 + 二分
🎯
下标列表 + 二分
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

(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 次询问的答案。

子任务:

子任务分值nqmax Aᵢ
130≤ 100≤ 100≤ 10
230≤ 10⁵≤ 10⁵≤ 10⁵
340≤ 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⁹ 大小的数组必爆)

需要解决的问题

02
思维导图
整理解题思路的全貌
📏 出现位置列表 + 二分
🧠 问题转化
问 [l, r] 内 x 的个数
等价于两个前缀次数之差
cnt(x, r) − cnt(x, l−1)
把"区间问题"降成"前缀问题"
🗂️ 数据结构
每个值 → 它出现的下标有序数组
用哈希表 / 平衡树当索引
总元素数恰为 n,与值域无关
值域 10⁹ 也从容处理
🔍 二分回答
upper_bound(P, r):P 中 ≤ r 的个数
lower_bound(P, l):P 中 < l 的个数
两者相减即答案
单次询问 O(log n)
⚠️ 易错点
x 不在 A 中要直接输出 0
下标要用 1 起的原始位置
l = 1 时 lower_bound 返回 0
多组数据之间要清空映射
03
样例手算推导
题面样例逐组手算 + "值域前缀和为什么不够通用"

🧮 题面样例(逐组手算)

样例输入是这样两组数据(第一组有环状重复,第二组是递增序列):

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,我们把它一条条算出来。

第 1 组:A = [7, 4, 6, 1, 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

第 2 组:A = [1, 2, 3, 4, 5]

值出现的下标列表 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 ✓

1
为什么第 2 条询问要减 lower_bound

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

2
第 4 条询问为什么是 1

P = [3],问 [1, 4]:

upper_bound(P, 4) = 1(下标 3 ≤ 4)

lower_bound(P, 1) = 0(没有下标 < 1)

相减 1 − 0 = 1

✅ 答案 1

3
加一条"查不存在的值"的验证

若问 (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)✅ 完全不受值域影响
1
子任务 2 的"标准做法"是什么

因为 max Aᵢ ≤ 10⁵,可以开 cnt[值][位置] 或

"对每个值维护一个前缀和数组"

甚至能 O(1) 回答一次询问

但它把"值域"当成了必须支付的成本

⚠️ 只对子任务 2 有效

2
子任务 3 为什么必须换思路

max Aᵢ 跳到 10⁹,任何"按值域开数组"的方案都要 10⁹ 级别空间

但序列只有 n ≤ 10⁵ 个数

也就是"值域稀疏、取值都挤在很小的一个子集里"

于是用映射把值离散化,只保留出现过的值

✅ 下标列表 + 二分

3
顺便说一下下限

建表扫描一遍 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。
04
解法对比
下标列表 + 二分 vs 值域桶 / 前缀和 vs 暴力扫描

⚔️ 解法对比

🟢 值 → 下标列表 + 两次二分 推荐

读入时为每个值记录它出现的下标(天然递增);询问时在对应列表上二分

  • 时间 O((n + q) log n)
  • 空间 O(n)
  • 与值域大小 完全无关
  • 代码约 25 行,稳过全部子任务
💡
为什么它是"通解":整张表的元素总数恰好是 n,再大的值域也只需要 O(n) 的空间。
而且询问被拆成两个"前缀计数",两个计数都能在同一条有序列表上二分出来,这就是"离线离散化 + 二分"这一套路的原型。

🟠 值域桶 / 逐值前缀和

开一个大小等于值域上界的桶数组,按值做前缀和

  • 询问 O(1)(最快)
  • 空间 O(max A) 或更多
  • max A ≤ 10⁵ 时可行
  • max A ≤ 10⁹ 时直接爆内存
⚠️
它的适用边界:只对子任务 1、2(值域 ≤ 10⁵)有效,能拿 60 分。
一旦进入子任务 3,10⁹ 个桶就是约 4 GB,这不是"慢一点"而是"根本开不出来"。

📈 性能对比

方案复杂度结论
下标列表 + 二分O((n + q) log n) / O(n)✅ 全子任务通吃
值域桶 + 前缀和O(1) 询问 / O(max A) 空间⚠️ 只有 60 分(值域小时才行)
每次询问暴力扫描O(nq) = 10¹⁰❌ 必超时
05
算法流程图
"值 → 下标列表"建表 + 逐询问两次二分
开始读入 T,共 T 组数据读入 n 与序列 A₁ … Aₙ建表:每个值映射到它出现的下标有序列表读入 q,准备逐行处理询问读入一行询问 (l, r, x)x 在建好的表里吗?在 ✓取出它的下标列表 P不在 ✗直接输出 0ans = upper_bound(P, r) − lower_bound(P, l),输出 ans这一组的 q 行询问都处理完了吗?T 组全处理完则结束,否则回到第 2 步换下一条询问
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📏 区间出现次数查询器

第一行输入 n 与 q,第二行输入 n 个整数(序列 A),接下来 q 行每行 l r x。程序用"值 → 下标列表 + 二分"逐条回答。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(值 → 出现下标列表 + 两次二分)

#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 的整段区间,逻辑一样,只是"索引"换成了排序 + 二分。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
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
题面样例:两组数据共 4 行输出
1
3
1 2 3
3
1 1 1
2 2 9
1 3 3
1
0
1
单点命中 / x 完全不在序列里 / 整段计数
1
3
1000000000 1000000000 1000000000
2
1 3 1000000000
2 2 1000000000
3
1
值域到 10⁹:只有下标列表方案能过(开桶必爆)
1
6
1 2 1 2 1 2
3
2 5 1
2 5 2
1 6 1
2
2
3
区间截断:注意 [2, 5] 两端的下标归属
1
4
5 5 5 5
2
1 4 5
3 3 6
4
0
全相同序列 / 查询一个根本不存在的值
✅
自查清单:① 是否为每个值建了有序下标列表?② x 不存在时输出 0 了吗?③ 是 upper_bound(P, r) − lower_bound(P, l) 吗?④ 多组数据之间清空了吗?

🚨 易错点清单

⚠️
x 不存在没特判:映射里查不到时答案必须是 0,新手常写成 pos[x].size(),容器不存在就出错。
⚠️
两个二分函数搞混:"≤ r" 用 upper_bound、"< l" 用 lower_bound,写反会让答案整体偏 1。
⚠️
下标基准不一致:列表里存的是 1 起的原始位置,如果用 0 起下标存储,就要把询问的 l, r 同步换算。
⚠️
忘记多组数据:T 组之间索引结构必须重来一遍,否则上一组的值会污染这一组。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + q) log n)
空间复杂度
O(n)
单次询问
两次二分 O(log n)
最坏运算量
约 2.5 × 10⁷

时间怎么算的?

空间都用在哪?

映射本身存 n 个键值对;所有下标列表的元素总数恰好是 n(每个位置只属于一个列表),再加上几个常数数组,空间是 O(n)。

✅ 与值域无关的 O(n) 空间,配合 O(log n) 的询问,是这道题唯一能通吃 40 分子任务的做法。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「值 -> 出现位置列表」+ 二分 的通用模板
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 的个数,这又变成了一个离线 + 树状数组的经典问题。把"值 → 位置"换成"位置 → 上一个同值位置",是这套离散化思想的常见升级方向。)