📝 题目大意

有 $N$ 个人排成一列，给定他们从前往后的编号序列 $P_1, P_2, \dots, P_N$。处理 $Q$ 个查询，每次给定两个编号 $A_i$ 和 $B_i$，输出站在更前面的那个人的编号。

💡 解题思路

1. 题目分析：题目本质上是在问：给定编号 $A$ 和 $B$，它们在序列 $P$ 中谁的下标更小（即谁更靠前）。注意输入保证 $A_i < B_i$（编号大小关系），但这与站位无关——站位由序列中出现的顺序决定。

2. 算法推导：

   • 朴素想法：每次查询时遍历 $P$ 数组，找到 $A$ 和 $B$ 各自的位置，比较后输出。这样每个查询 $O(N)$，总复杂度 $O(NQ)$，在 $N, Q \leq 100$ 下完全可行，但不够优雅。
   • 优化思路：注意到 $P_i$ 是 $1$ 到 $N$ 的一个排列，我们可以建立一个反向映射——pos[x] 表示编号为 $x$ 的人在队伍中的位置（第几位）。读入时，对于第 $i$ 个读入的 $p$，令 pos[p] = i。
   • 查询时，直接比较 pos[A] 和 pos[B]：位置更小的人站在更前面，输出其编号即可。每个查询 $O(1)$。

3. 边界与细节：

   • 编号从 $1$ 开始，因此 pos 数组需要开到 $N+1$。
   • 题目保证 $A_i \neq B_i$，且根据条件 $A_i < B_i$ 仅指数值大小，不代表站位顺序，不要被误导。
   • 由于 pos[p] 的值域是 $[1, N]$，不会出现位置相等的情况，无需处理平局。

⏱️ 复杂度分析

• 时间复杂度：读入并建立 pos 数组 $O(N)$，每个查询 $O(1)$，总复杂度 $O(N + Q)$。
• 空间复杂度：pos 数组占用 $O(N)$ 额外空间。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int N;
    cin >> N;
    // pos[x] 表示编号为 x 的人站在第几个位置（1-indexed）
    vector<int> pos(N + 1);
    for (int i = 1; i <= N; i++) {
        int p;
        cin >> p;
        pos[p] = i; // 编号 p 的人在第 i 位
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int A, B;
        cin >> A >> B;
        // 位置更小的那个人站在更前面
        if (pos[A] < pos[B]) {
            cout << A << endl;
        } else {
            cout << B << endl;
        }
    }
    return 0;
}