你好！我是你的OI信息学奥赛教练。很高兴能带你一起攻克这道 GESP 八级的题目。

这道题目虽然出现在八级考题中，但它的核心考察点其实非常纯粹：STL容器的运用与二分查找思想。只要转换一下观察角度，这道题就会迎刃而解。

一、 💡 输入题目的思路提示

1. 为什么暴力法不行？

首先，我们看一眼数据范围。$n, q \le 10^5$。 如果你对于每次询问，都写一个 for (int j = l; j <= r; j++) 去遍历统计，那么最坏情况下的运算量是 $10^5 \times 10^5 = 10^{10}$ 次。 而计算机一秒钟大约只能跑 $10^8$ 次运算。暴力法一定会超时（TLE）。

2. 逆向思维：倒排索引

暴力法是“拿着区间去找数字”，我们能不能反过来，“记下每个数字出现的所有位置”？

比如数列 A = [1, 5, 2, 5, 3, 5]，下标从 1 开始。

• 数字 1 出现在：{1}
• 数字 2 出现在：{3}
• 数字 3 出现在：{5}
• 数字 5 出现在：{2, 4, 6}

现在询问：l=2, r=5, x=5。 也就是问：在下标区间 [2, 5] 里，有几个 5？ 这就转化成了：在列表 {2, 4, 6} 中，有几个数是 $\ge 2$ 且 $\le 5$ 的？ 答案显然是 2 个（即 2 和 4）。

3. 处理大数值

题目中 $A_i \le 10^9$，这意味着我们不能开一个数组 vector<int> pos[1000000000]。内存会爆炸。 我们需要一个能处理“稀疏大整数索引”的容器。C++ 的 std::map 或者离散化是好帮手。

4. 快速统计

对于一个有序的下标列表（比如 {2, 4, 6, 9, 12}），如何快速找到 $\ge l$ 且 $\le r$ 的元素个数？ 不要遍历！要使用二分查找。

二、 📚 预备知识点

解决这道题，你需要熟练掌握以下工具：

1. std::vector：用于存储某个数字出现的所有下标列表。
2. std::map：用于建立 数值 -> 下标列表 的映射（因为数值高达 $10^9$）。
3. 二分查找函数 (std::lower_bound / std::upper_bound)：
   • lower_bound(v.begin(), v.end(), l)：找到第一个 $\ge l$ 的位置。
   • upper_bound(v.begin(), v.end(), r)：找到第一个 $> r$ 的位置。
   • 两者迭代器相减，就是区间内的个数。

三、 📝 草稿纸上的推演（教学模式）

假设我们在黑板前，数据是： $N=6$，序列 $A = \{7, 4, 6, 7, 7, 1\}$ 询问：$l=2, r=5, x=7$

步骤 1：预处理（建立映射） 我们遍历数组，把每个数的下标“扔”进对应的桶里。

• 遇到 $A_1=7$ $\rightarrow$ map[7] = {1}
• 遇到 $A_2=4$ $\rightarrow$ map[4] = {2}
• 遇到 $A_3=6$ $\rightarrow$ map[6] = {3}
• 遇到 $A_4=7$ $\rightarrow$ map[7] = {1, 4}
• 遇到 $A_5=7$ $\rightarrow$ map[7] = {1, 4, 5}
• 遇到 $A_6=1$ $\rightarrow$ map[1] = {6}

步骤 2：处理询问 我们要查 $x=7$ 在 $[2, 5]$ 出现的次数。

1. 去 map 里找 7。找到了！对应的下标列表是 v = {1, 4, 5}。注意，这个列表是天然有序的。
2. 问题转化为：在有序数组 {1, 4, 5} 中，有多少个数在 $[2, 5]$ 之间？
3. 使用二分查找：
   • 找到第一个 $\ge 2$ 的位置：是 4（下标索引为 1）。
   • 找到第一个 $> 5$ 的位置：是 end()（越界了，下标索引为 3）。
   • 个数 = 索引相减 = $3 - 1 = 2$。

复杂度分析：

• 预处理：遍历 $N$ 个数，每次插入 map 是 $O(\log N)$（假设 map 元素个数接近 N），总共 $O(N \log N)$。
• 查询：每次去 map 找 vector 是 $O(\log N)$，在 vector 里二分是 $O(\log N)$。总共 $O(Q \log N)$。
• 总计：$O((N+Q) \log N)$。对于 $10^5$ 的数据，运算量级在 $10^6 \sim 10^7$，完全可以通过。

四、 🗝️ 读题关键词总结

• “区间 ... 出现的次数” $\rightarrow$ 这是一个经典的静态区间查询问题。
• “$A_i$ 很大 ($10^9$)” $\rightarrow$ 不能直接用数组下标计数，必用 map 或离散化。
• “多次询问” $\rightarrow$ 需要预处理，不能每次 $O(N)$ 扫描。

五、 💻 标准代码 (C++14)

/**
 * P10288 [GESP样题 八级] 区间
 * 算法: Map + Vector + 二分查找
 * 时间复杂度: O(T * (N log N + Q log N))
 * 空间复杂度: O(N)
 */

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    if (!(cin >> n)) return;

    // 使用 map 存储：数值 -> 该数值出现的所有下标列表
    // 键是 A_i (最大 10^9)，值是 vector<int>
    map<int, vector<int>> positions;

    // 1. 预处理：构建倒排索引
    for (int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        // 将当前下标 i 加入到 val 的列表中
        // 由于是从左到右遍历，vector 中的下标自然是有序的
        positions[val].push_back(i);
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;

        // 2. 查询
        // count() 检查 x 是否存在，避免访问不存在的键导致创建空 vector (虽然不影响正确性但略微影响性能)
        if (positions.count(x) == 0) {
            cout << 0 << "\n";
            continue;
        }

        // 获取 x 的所有下标列表引用
        const vector<int> &vec = positions[x];

        // 核心：在 vec 中查找范围 [l, r] 内的元素个数
        // lower_bound 找第一个 >= l 的迭代器
        // upper_bound 找第一个 > r 的迭代器
        // 两个迭代器相减即为中间的元素个数
        auto it_start = lower_bound(vec.begin(), vec.end(), l);
        auto it_end = upper_bound(vec.begin(), vec.end(), r);

        cout << (it_end - it_start) << "\n";
    }
}

int main() {
    // 开启 IO 加速，这是竞赛标准操作
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

关键点与易错点注释：

1. 多组数据清空：由于 map 是在 solve() 函数内定义的局部变量，每次函数结束会自动销毁，所以不需要手动 .clear()。如果是全局变量，千万别忘了清空。
2. positions[x] 的副作用：如果 map 中不存在 x，直接写 positions[x] 会自动创建一个空的 vector 插入 map 中。虽然逻辑没错（空 vector 查出来也是 0），但如果恶意构造大量不存在的查询，可能会增加内存开销。使用 count 或 find 先判断更严谨。
3. 引用优化：const vector<int> &vec = positions[x]; 这里一定要用引用 &，否则会发生 vector 的拷贝，导致巨大的时间开销（TLE）。

六、 🧪 数据生成器 (用于测试)

这是一份功能完整的数据生成器，包含对边界情况（如 $x$ 不存在、区间只有一个点等）的覆盖。

/**
 * P10288 数据生成器
 * 生成 1.in/out ~ 10.in/out
 */
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <random>
#include <string>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成答案)
// ==========================================
class Solver {
public:
    void solve_one(istream& in, ostream& out) {
        int n;
        if (!(in >> n)) return;
        
        map<int, vector<int>> positions;
        for (int i = 1; i <= n; ++i) {
            int val;
            in >> val;
            positions[val].push_back(i);
        }

        int q;
        in >> q;
        while (q--) {
            int l, r, x;
            in >> l >> r >> x;
            
            if (positions.find(x) == positions.end()) {
                out << 0 << "\n";
            } else {
                const auto& vec = positions[x];
                auto it1 = lower_bound(vec.begin(), vec.end(), l);
                auto it2 = upper_bound(vec.begin(), vec.end(), r);
                out << (it2 - it1) << "\n";
            }
        }
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(std::random_device{}());

int rand_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

void generate_data(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fout(in_name);

    int T = 5; 
    // 根据 ID 调整难度
    int N_max = (id <= 3) ? 100 : 100000;
    int Q_max = (id <= 3) ? 100 : 100000;
    int A_max = (id <= 3) ? 10 : (id <= 6 ? 100000 : 1000000000);
    
    // 如果是大点，适当减少 T 以防止文件过大，但题目要求总和可能有限制，这里简单处理
    if (id > 3) T = 2; 

    fout << T << "\n";
    while (T--) {
        int n = rand_int(N_max / 2, N_max);
        int q = rand_int(Q_max / 2, Q_max);
        fout << n << "\n";
        
        vector<int> vals;
        for (int i = 0; i < n; ++i) {
            int val = rand_int(1, A_max);
            fout << val << (i == n - 1 ? "" : " ");
            vals.push_back(val);
        }
        fout << "\n";
        
        fout << q << "\n";
        for (int i = 0; i < q; ++i) {
            int l = rand_int(1, n);
            int r = rand_int(l, n);
            int x;
            // 构造查询：80% 概率查询存在的数，20% 概率查询随机数
            if (rand_int(1, 10) <= 8 && !vals.empty()) {
                x = vals[rand_int(0, n - 1)];
            } else {
                x = rand_int(1, A_max);
            }
            fout << l << " " << r << " " << x << "\n";
        }
    }
    fout.close();

    // 生成输出
    ifstream fin(in_name);
    ofstream f_ans(out_name);
    Solver s;
    int t_in;
    if (fin >> t_in) {
        while(t_in--) s.solve_one(fin, f_ans);
    }
    fin.close();
    f_ans.close();
    
    cout << "Generated Case " << id << endl;
}

int main() {
    for (int i = 1; i <= 10; ++i) generate_data(i);
    return 0;
}