题解：货运列车车厢记录分析

问题分析

本题要求判断 Bajtek 记录的每节车厢是否“可能”出现在 Bitek 的记录中（即是否存在至少一种子序列匹配方式包含该车厢）。核心要点：

1. Bitek 的列表是 Bajtek 列表的子序列（可通过删除部分元素得到，顺序不变）。
2. 对于 Bajtek 中的第 (i) 节车厢，若存在至少一种子序列匹配方式包含它，则输出 1，否则输出 0。

关键思路

要判断某节车厢是否可能被 Bitek 记录，需满足两个条件：

1. 该车厢在 Bitek 的列表中存在对应位置（即类型匹配）。
2. 存在一种子序列匹配方式，使得该车厢既能匹配 Bitek 列表中的某个位置，又能保证前后车厢的匹配逻辑自洽。

核心算法：通过两次遍历预处理，标记每个车厢是否满足上述条件：

1. 反向遍历：记录 Bitek 列表中每个元素在 Bajtek 列表中最晚可能出现的位置（last 数组）。
2. 正向遍历：记录 Bitek 列表中每个元素在 Bajtek 列表中最早可能出现的位置（通过 pos 数组跟踪），并结合 last 数组判断当前车厢是否可能被包含。

代码解析

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 3e5 + 5;

int n, m, k, a[MAXN], b[MAXN], last[MAXN], pos[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &k);

    // 读取Bajtek的车厢序列（1-based索引）
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    // 读取Bitek的车厢序列（1-based索引）
    for (int i = 1; i <= m; i++)
        scanf("%d", &b[i]);

    // 第一步：反向遍历，计算last[j]：Bitek的第j个元素在Bajtek中最晚出现的位置
    for (int i = n, j = m; i >= 1; i--) {
        if (a[i] == b[j]) {  // 找到匹配的元素
            last[j] = i;     // 记录最晚位置
            j--;             // 继续匹配前一个元素
        }
    }

    // 第二步：正向遍历，判断每个车厢是否可能被记录
    for (int i = 1, j = 1; i <= n; i++) {
        if (a[i] == b[j]) {  // 找到匹配的元素
            pos[a[i]] = j;   // 记录Bitek中当前匹配的位置（最早可能位置）
            j++;             // 继续匹配下一个元素
        }

        // 判断条件：
        // 1. pos[a[i]] != 0：该车厢类型在Bitek中存在匹配位置
        // 2. last[pos[a[i]]] >= i：该位置不晚于最晚可能出现的位置
        if (pos[a[i]] != 0 && last[pos[a[i]]] >= i)
            printf("1 ");
        else
            printf("0 ");
    }

    return 0;
}

关键步骤详解

1. 反向遍历计算 last 数组：

   • 从 Bajtek 列表末尾开始遍历，同步匹配 Bitek 列表的末尾元素。
   • 对于 Bitek 列表的第 (j) 个元素，last[j] 存储它在 Bajtek 中最晚可能出现的位置（确保后续元素有足够空间匹配）。

2. 正向遍历判断可能性：

   • 从 Bajtek 列表开头开始遍历，同步匹配 Bitek 列表的开头元素。
   • pos[x] 记录类型为 (x) 的车厢在 Bitek 列表中最早匹配的位置。
   • 对于当前车厢 (a[i])，若其类型在 Bitek 中存在匹配（pos[a[i]] != 0），且当前位置 (i) 不晚于该匹配位置的最晚可能出现位置（last[pos[a[i]]] >= i），则该车厢可能被记录（输出 1），否则输出 0。

复杂度分析

• 时间复杂度：(O(n + m))。两次遍历均为线性时间，适用于 (n, m \leq 3 \times 10^5) 的数据范围。
• 空间复杂度：(O(n + m + k))。存储两个序列及辅助数组，空间开销可控。

样例验证

以样例 1 为例：

• Bajtek 序列：[1, 3, 2, 1, 2, 3, 1, 3, 2]
• Bitek 序列：[1, 3, 1, 2]

反向遍历得到 last 数组：

• last[4] = 9（Bitek 第 4 个元素 2 在 Bajtek 中最晚位置为 9）
• last[3] = 7（Bitek 第 3 个元素 1 在 Bajtek 中最晚位置为 7）
• last[2] = 6（Bitek 第 2 个元素 3 在 Bajtek 中最晚位置为 6）
• last[1] = 4（Bitek 第 1 个元素 1 在 Bajtek 中最晚位置为 4）

正向遍历判断：

• 例如第 3 节车厢 2：Bitek 中无对应位置（pos[2] 未被赋值），输出 0。
• 第 4 节车厢 1：pos[1] = 1 且 last[1] = 4 >= 4，输出 1。

最终输出与样例一致，验证了算法的正确性。

该解法通过两次遍历高效标记可能被记录的车厢，兼具时间和空间效率，完美适配题目需求。