📝 题目大意

给定一个长度为 $3N$ 的序列，其中 $1 \sim N$ 每个数字恰好出现 $3$ 次。对于每个数字 $i$，定义 $f(i)$ 为它第二次出现的位置下标。要求将 $1 \sim N$ 按照 $f(i)$ 的升序排列并输出。

💡 解题思路

1. 题目分析：

   • $N \leq 10^5$，序列长度 $3N \leq 3 \times 10^5$，需要 $O(N)$ 或 $O(N \log N)$ 的算法。
   • 每个数字恰好出现 $3$ 次，因此我们只需要关心每个数字的第二次出现位置。
   • 由于 $f(i)$ 就是第二次出现的位置，题目本质是：找出每个数字第二次出现的位置，并按该位置排序输出对应数字。

2. 算法推导：

   • 遍历序列，维护两个数组 first[a] 和 second[a]，分别记录数字 $a$ 第一次和第二次出现的位置。
   • 当 first[a] == -1 时，记录当前位置为第一次出现；当 first[a] 已记录但 second[a] == -1 时，记录当前位置为第二次出现（即 $f(a)$）。
   • 第三次出现不需要处理，因为我们只关心第二次出现。
   • 遍历完成后，将 $(second[i], i)$ 作为 pair 存入数组 order，对 order 按 second[i] 升序排序。
   • 最后按排序后的顺序输出每个数字 $i$。

3. 边界与细节：

   • 数组下标从 $1$ 开始，所以 first 和 second 开到 $N+1$ 的大小。
   • 位置编号从 $1$ 开始，与题目定义一致。
   • 输出格式要求数字间用空格分隔，行末不能有多余空格——代码中通过 if (i > 0) cout << " "; 来保证。

⏱️ 复杂度分析

• 时间复杂度：$O(N \log N)$，遍历序列 $O(N)$，排序 $O(N \log N)$。
• 空间复杂度：$O(N)$，需要存储 first、second 和 order 数组。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    // first[a] 记录数字 a 第一次出现的位置，second[a] 记录第二次出现的位置（即 f(a)）
    vector<int> first(N + 1, -1);
    vector<int> second(N + 1, -1);
    
    // 遍历整个序列，记录每个数字的前两次出现位置
    for (int pos = 1; pos <= 3 * N; pos++) {
        int a;
        cin >> a;
        if (first[a] == -1) {
            first[a] = pos;          // 第一次出现
        } else if (second[a] == -1) {
            second[a] = pos;          // 第二次出现，即 f(a)
        }
        // 第三次出现无需记录
    }
    
    // 将每个数字和它的 f(i) 配对
    vector<pair<int, int>> order; 
    for (int i = 1; i <= N; i++) {
        order.push_back({second[i], i}); // {f(i), 数字 i}
    }
    
    // 按 f(i) 升序排序
    sort(order.begin(), order.end());
    
    // 输出排序后的数字序列
    for (int i = 0; i < N; i++) {
        if (i > 0) cout << " ";     // 控制空格，避免行末多余空格
        cout << order[i].second;
    }
    cout << endl;
    return 0;
}