题目描述

模拟一个角色扮演游戏的进度。游戏有 $N$ 个剧情点（编号 1 到 N）。玩家可以通过不同的操作从一个剧情点移动到另一个剧情点。游戏允许在特定剧情点存档，也可以读取之前的存档回到保存的剧情点。

游戏流程定义：
对于每个剧情点 $i$（$1 \le i \le N$），有 $K_i$ 种操作或选择。执行第 $k$ 种选择（$1 \le k \le K_i$）会将玩家移动到指定的下一个剧情点。

玩家操作：
共有 $M$ 次操作，按顺序进行。操作类型有三种：
1. 类型 0 (选择)： 0 j - 表示玩家在当前剧情点做出了第 $j$ 个选择（$j$ 是 1-based index），移动到对应的下一个剧情点。保证选择是合法的。
2. 类型 1 (存档)： 1 j - 表示玩家在当前剧情点进行存档，将当前剧情点的编号保存在第 $j$ 个存档位（$j$ 是 1-based index，最多 100 个档位）。需要输出存档时的剧情点编号。
3. 类型 2 (读档)： 2 j - 表示玩家读取第 $j$ 个存档位中保存的剧情点，将当前剧情点设置为读取到的编号。

初始状态：
游戏从剧情点 1 开始。

任务：
模拟这 $M$ 次操作，按要求输出：
每次执行类型 1 (存档) 操作时，输出被存档的剧情点编号。
在所有 $M$ 次操作完成后，输出玩家最终所在的剧情点编号。

样例

输入:
10 11
3 2 3 4
1 6
3 4 7 5
1 3
1 9
2 3 5
3 1 8 5
1 9
2 8 10
0
1 1
0 3
0 1
1 2
0 2
0 2
2 2
0 3
0 1
1 1
0 2

输出:

1
3
9
10

样例解释

• 开始于剧情点 1。
• 1 1: 存档点 1 -> 输出 1。当前点 1。存档 slot[1] = 1。
• 0 3: 在点 1 做第 3 个选择 -> 移动到点 4。当前点 4。
• 0 1: 在点 4 做第 1 个选择 -> 移动到点 3。当前点 3。
• 1 2: 存档点 3 -> 输出 3。当前点 3。存档 slot[2] = 3。
• 0 2: 在点 3 做第 2 个选择 -> 移动到点 7。当前点 7。
• 0 2: 在点 7 做第 2 个选择 -> 移动到点 8。当前点 8。
• 2 2: 读档 slot 2 (存的是点 3) -> 移动到点 3。当前点 3。
• 0 3: 在点 3 做第 3 个选择 -> 移动到点 5。当前点 5。
• 0 1: 在点 5 做第 1 个选择 -> 移动到点 9。当前点 9。
• 1 1: 存档点 9 -> 输出 9。当前点 9。存档 slot[1] = 9。
• 0 2: 在点 9 做第 2 个选择 -> 移动到点 10。当前点 10。
• 所有操作结束，最终在点 10 -> 输出 10。

算法 (直接模拟)

$O(N + \sum K_i + M)$

思路分析

这个问题是一个直接的模拟题。我们需要根据输入的操作序列，一步一步地更新玩家的当前状态（即所在的剧情点编号），并处理存档和读档操作。

1. 表示游戏结构:
   游戏剧情点之间的转移关系可以看作一个有向图。每个剧情点是一个节点。从剧情点 $i$ 出发，如果有 $K_i$ 个选择，那么就有 $K_i$ 条出边，分别指向选择对应的下一个剧情点。
   我们可以使用邻接表来存储这个图。std::vector<std::vector<int>> adj，其中 adj[i] 是一个 vector，存储从剧情点 i 出发可以到达的所有剧情点编号。特别地，adj[i][k-1] 存储的是做出第 k 个选择（1-based）后到达的剧情点编号（因为 vector 是 0-based index）。

2. 表示存档:
   我们需要存储每个存档位对应的剧情点编号。由于存档位最多 100 个，且编号从 1 开始，我们可以使用一个大小为 101 的数组（或 vector） saves，saves[j] 存储第 $j$ 个档位保存的剧情点编号。

3. 模拟状态:
   我们需要一个变量 curr 来存储玩家当前所在的剧情点编号。初始时 curr = 1。

4. 处理操作:
   我们需要循环 $M$ 次，读取每次操作的类型 op 和参数 j。

   • 如果 op == 0 (选择):
     读取选择编号 j。根据图的结构，找到当前剧情点 curr 做第 j 个选择后到达的下一个剧情点。这个目标点存储在 adj[curr][j-1] (注意 j 是 1-based，vector 下标是 0-based)。更新 curr = adj[curr][j-1]。
   • 如果 op == 1 (存档):
     读取存档位编号 j。将当前的剧情点编号 curr 存入 saves[j]。同时，按照要求，输出 curr。
   • 如果 op == 2 (读档):
     读取存档位编号 j。从 saves[j] 中读取之前保存的剧情点编号，并将其赋值给 curr，即 curr = saves[j]。

5. 最终输出:
   在 $M$ 次操作全部完成后，输出最终的 curr 值。

时间复杂度

• 读取输入和构建图: 读取 N, M 是 O(1)。读取 N 行剧情点设定，总共需要读取 $N + \sum K_i$ 个整数，构建邻接表的时间复杂度是 $O(N + \sum K_i)$。题目保证 $\sum K_i \le 10^6$。
• 初始化: 初始化 saves 数组和 curr 变量是 O(1) 或 O(存档位数)。
• 模拟 M 次操作: 每次操作 (选择、存档、读档) 的时间复杂度都是 O(1)（数组/vector 访问和赋值）。因此，模拟 M 次操作的总时间是 O(M)。
• 总时间复杂度: $O(N + \sum K_i + M)$。考虑到数据范围 $N, M \le 10^5$ 且 $\sum K_i \le 10^6$，这个复杂度是完全可行的。

空间复杂度

• 存储图的邻接表 adj: 空间复杂度为 $O(N + \sum K_i)$。
• 存储存档 saves: 空间复杂度为 O(存档位数)，即 O(101) 或 O(1)。
• 其他变量：O(1)。
• 总空间复杂度: $O(N + \sum K_i)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;

// 定义类型别名 (虽然本题未使用 i64 等)
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    std::ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    std::cin.tie(nullptr);

    int n, m; // N: 剧情点数量, M: 操作数量
    std::cin >> n >> m;

    // 使用邻接表存储图结构
    // adj[i] 是一个 vector，存储从剧情点 i 出发可以到达的剧情点
    // 大小设为 n + 1 以方便使用 1-based 索引
    std::vector<std::vector<int>> adj(n + 1);
    // 读取每个剧情点的后续发展设定
    for (int i = 1; i <= n; ++i) { // 遍历剧情点 1 到 N
        int k; // 从剧情点 i 出发的选择数量
        std::cin >> k;
        adj[i].resize(k); // 调整邻接表大小
        // 读取 k 个选择对应的目标剧情点
        for (int choice_idx = 0; choice_idx < k; ++choice_idx) {
            // adj[i][choice_idx] 存储做出第 (choice_idx + 1) 个选择后到达的点
            std::cin >> adj[i][choice_idx];
        }
    }

    // 使用 vector 存储存档信息，大小 101 处理档位 1 到 100
    // saves[j] 存储第 j 个档位保存的剧情点编号
    std::vector<int> saves(101); // 默认初始化为 0
    // 初始化当前剧情点为 1
    int curr = 1;

    // 模拟 M 次操作
    for (int op_count = 0; op_count < m; ++op_count) {
        int op, j; // 操作类型 op, 操作参数 j
        std::cin >> op >> j;

        // 处理类型 0：选择操作
        if (op == 0) {
            // 根据当前点 curr 和选择 j (1-based)，找到下一个点
            // 需要使用 j-1 作为 vector 的索引
            curr = adj[curr][j - 1];
        // 处理类型 1：存档操作
        } else if (op == 1) {
            // 将当前点 curr 保存到档位 j
            saves[j] = curr;
            // 按要求输出存档时的剧情点编号
            std::cout << curr << "\n";
        // 处理类型 2：读档操作
        } else { // op == 2
            // 从档位 j 读取存档点，更新当前点
            curr = saves[j];
        }
    }

    // 所有操作结束后，输出最终所在的剧情点编号
    std::cout << curr << "\n";

    return 0; // 程序正常结束
}