P3156 【深基15.例1】询问学号

题目描述

有 \(n(n \le 2 \times 10^6)\) 名同学陆陆续续进入教室。我们知道每名同学的学号（在 \(1\) 到 \(10^9\) 之间），按进教室的顺序给出。上课了，老师想知道第 \(i\) 个进入教室的同学的学号是什么（最先进入教室的同学 \(i=1\)），询问次数不超过 \(10^5\) 次。

输入格式

第一行 \(2\) 个整数 \(n\) 和 \(m\)，表示学生个数和询问次数。

第二行 \(n\) 个整数，表示按顺序进入教室的学号。

第三行 \(m\) 个整数，表示询问第几个进入教室的同学。

输出格式

输出 \(m\) 个整数表示答案，用换行隔开。

输入输出样例 #1

输入 #1

10 3
1 9 2 60 8 17 11 4 5 14
1 5 9

输出 #1

1
8
5

Tip

b站讲解链接

📌 题目分析

给定数据：

n 名同学，学号在 1 到 10^9 之间 (n ≤ 2 × 10^6)
m 次询问，每次问第 i 个进入教室的学号 (m ≤ 10^5)

要求按照查询的序号，快速报出对应的学号。

👉 本质：

线性存储结构的数据录入与随机访问

👉 类型：

数组 / std::vector 基础模板题

🧠 解题思路

1️⃣ 为什么选用数组或 Vector？

题目要求我们记录多达 200 万个数据，并且要在 \(10^5\) 次询问中，每次都能瞬间（\(O(1)\) 时间复杂度）找到第 \(i\) 个数据。 内存中连续排列的数组（或者 C++ STL 中的 std::vector）天然具备通过下标（索引）进行 \(O(1)\) 极速访问的能力，是这道题的唯一指定解法。

2️⃣ 偏移量的处理（0-indexed vs 1-indexed）

C++ 中数组的下标默认是从 0 开始的。 但是题目中的询问是自然语言描述的：“第 \(i\) 个同学”，也就是从 1 开始。 * 方法一：存储时依然从 0 存起（存到 n-1），当查询第 i 个时，输出下标为 i - 1 的数据。 * 方法二（推荐）：直接从下标 1 开始存（存到 n）。这样查询第 i 个时，直接输出下标为 i 的数据，做到“所见即所得”，极大地降低了脑抽写错边界的概率。

3️⃣ 空间复杂度计算

最大需要存储 \(2 \times 10^6\) 个 int 类型的整数。 一个 int 占 4 字节。 \(2,000,000 \times 4 \text{ Bytes} \approx 8 \text{ MB}\)。 一般的算法竞赛题目空间限制都在 128MB 甚至 256MB 以上，所以直接开一个这么大的数组是完全合法且安全的。

4️⃣ 时间复杂度

• 录入 \(n\) 个数据：遍历一次，时间 \(O(n)\)。
• 处理 \(m\) 次查询：每次 \(O(1)\)，总时间 \(O(m)\)。
• 总时间复杂度：\(O(n + m)\)。 算法逻辑上已经是最优解，但由于输入量极大，这道题真正的核心考验在于输入输出的速度。

---

💻 C++代码

#include <iostream>
#include <vector>

using namespace std;

// 使用全局数组也是可以的：int a[2000005];
// 这里使用 vector 是更现代的 C++ 写法
vector<int> stu;

int main() {
    // ！！！绝密武器：解除 C++ 输入输出流的绑定，极大提升读写速度 ！！！
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // 因为我们要从下标 1 开始存，所以数组大小开到 n + 1
    stu.resize(n + 1);

    // 录入 n 个同学的学号，从下标 1 存到 n
    for (int i = 1; i <= n; i++) {
        cin >> stu[i];
    }

    // 处理 m 次询问
    for (int i = 0; i < m; i++) {
        int query_index;
        cin >> query_index;
        // 直接通过下标 O(1) 访问并输出
        cout << stu[query_index] << "\n";
    }

    return 0;
}

---

⚠️ 易错点

❌ 1. 惨遭 TLE（超时）的输入输出陷阱

这道题是洛谷专门用来给新手上“快读”这一课的。 数据的输入量达到了恐怖的 \(2 \times 10^6\) 个。如果你只是老老实实写了 cin >> 和 endl，由于 C++ 标准输入流的同步机制和缓冲区刷新开销，程序绝对会超时（TLE）。 破局之法：必须加上 ios::sync_with_stdio(false); cin.tie(nullptr);，且所有的换行必须用 \n 替代 endl。

❌ 2. 数组开在 main 函数里面导致爆栈 (RE)

如果你选择用原生数组而不是 vector，写了 int a[2000005];，千万不能把它写在 main 函数里面！ 在函数内部定义的局部变量会被分配在“栈区 (Stack)”，而栈区的大小通常只有几 MB。200万个 int 放进去会瞬间把栈撑爆，引发 Runtime Error（段错误）。 破局之法：原生大数组必须写在 main 函数外面（全局变量区），或者像代码中那样使用 vector（底层在堆区 Heap 动态分配）。

❌ 3. 数组下标越界

如果从 0 开始存，却输出了 stu[query_index]，当查询序号为 n 时，就会访问到不属于你的内存空间。统一对齐基准（要么输入输出都减 1，要么直接从 1 开始存）是预防此类 bug 的唯一法则。

---

🚀 一句话总结

数组下标 O(1) 闪电寻址 + 解除流绑定开启狂暴读写 = 完美通关。

---

🔥 补充

硬核知识点：C++ 读入优化的鄙视链

在面对千万级别输入数据的变态题目时，各种读取方式的速度是有着严密层级的（速度从慢到快）：

1. 最慢龟速：默认状态下的 cin / cout 搭配 endl。（本题直接 TLE）
2. C 语言原生：scanf / printf。（速度很快，足以通过本题，是很多老派 OIer 的最爱）
3. 解除封印的 C++：加了 ios::sync_with_stdio(0); cin.tie(0); 的 cin / cout。（速度追平甚至略超 scanf，是日常刷题性价比最高的写法）
4. 手写快读 (Fast I/O)： 利用 getchar() 逐个读取字符，然后自己用数学公式拼成整数。因为避开了所有的格式化判断，速度极其狂暴。

   inline int read() {
       int x = 0, f = 1; char ch = getchar();
       while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
       while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
       return x * f;
   }
   // 使用：int n = read();
   

5. fread 终极黑魔法：不仅手写转换，还直接动用底层系统调用 fread 一次性把文件里的几 MB 数据全搬进内存再慢慢抠字符。这种写法通常只有在卷省选（NOI）且常数被卡得极其严重时才会祭出。对于入门和普及组，掌握到第 3 层或第 4 层就天下无敌了。