题意

$1$ 号同学先入队。$2\sim N$ 号同学依次插入到某个已入队同学的左边或右边。随后有 $M$ 次删除（可能删除已删除的同学，需忽略）。最后输出从左到右的同学编号。

思路

$N \leqslant 10^5$，$M \leqslant N$。如果用数组或 vector 直接模拟，每插入/删除一次可能需要移动大量元素，最坏 $O(N^2)$，会超时。

先看一个正确但只适合小数据的暴力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * date: 2026-07-07 00:00:00
 */
// brute.cpp：小数据暴力解，用 vector 模拟插入和删除。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> q;         // 队列，存储从左到右的同学编号
    q.push_back(1);        // 1 号同学初始在最左侧

    // 处理插入
    for (int i = 2; i <= n; i++) {
        int k, p;
        cin >> k >> p;
        // 找到 k 号同学在队列中的位置
        auto it = find(q.begin(), q.end(), k);
        if (p == 0) {
            q.insert(it, i);  // 插到 k 左边
        } else {
            q.insert(it + 1, i); // 插到 k 右边
        }
    }

    int m;
    cin >> m;
    // 处理删除
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        auto it = find(q.begin(), q.end(), x);
        if (it != q.end()) {
            q.erase(it);
        }
    }

    // 输出最终队列
    for (int x : q) cout << x << ' ';
    cout << '\n';

    return 0;
}

暴力的瓶颈在于 find + insert/erase，每次操作的代价跟当前队列长度成正比。

其实，插入一个同学只影响他插入位置相邻的两个同学。双向链表恰好支持 $O(1)$ 的「在指定节点左侧/右侧插入」和「删除指定节点」。题目的操作完美对应：

• 插入到 k 左边：修改 L[k]、R[L[k]]、L[i]、R[i]
• 插入到 k 右边：修改 R[k]、L[R[k]]、L[i]、R[i]
• 删除 x：修改 R[L[x]] 和 L[R[x]]，将 x 标记为已删除

由于题目直接用编号引用同学，我们用数组 L[i] / R[i] 记录编号 i 的左、右邻居。数组下标即节点，不需要指针，适合竞赛写法和调试。

指针变化示意

这张表展示把新同学 i 插入到同学 k 左边时，数组双向链表需要改哪些指针：

插入到右边是完全对称的：先记住 right_k = R[k]，再让 k <-> i <-> right_k 连起来。 这里的核心是只修改相邻几个点，不移动整个序列。 删除 x 也是同样思想，把 L[x] 和 R[x] 直接接起来即可。

删除时不是等到输出时跳过，而是直接把 x 从链表中摘除。del[x] 的作用是记录这个同学已经被删除过，避免第二次删除同一个编号时重复修改链表。

遍历输出时先找到链表头（没有左邻居且未被删除的节点），然后沿 R[] 向右输出。

Python 知识

• left/right 两个列表按学生编号直接索引，作用与 C++ 数组相同，但无需预设固定最大值。
• tokens=iter(map(int,sys.stdin.buffer.read().split())) 配合 next(tokens) 按题面顺序消费大量纯整数。
• next((student for ...),0) 查找表头；若所有人都删除，默认返回 0。
• 列表 removed 保存布尔状态，重复删除时直接跳过。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：整数 token 迭代器输入。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：next(generator,default) 查找首个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45import sys


tokens = iter(map(int, sys.stdin.buffer.read().split()))
n = next(tokens)
left = [0] * (n + 1)
right = [0] * (n + 1)
removed = [False] * (n + 1)

for student in range(2, n + 1):
    neighbor, side = next(tokens), next(tokens)
    if side == 0:
        previous = left[neighbor]
        left[student], right[student] = previous, neighbor
        left[neighbor] = student
        if previous:
            right[previous] = student
    else:
        following = right[neighbor]
        left[student], right[student] = neighbor, following
        right[neighbor] = student
        if following:
            left[following] = student

for _ in range(next(tokens)):
    student = next(tokens)
    if removed[student]:
        continue
    removed[student] = True
    previous, following = left[student], right[student]
    if previous:
        right[previous] = following
    if following:
        left[following] = previous

head = next(
    (student for student in range(1, n + 1) if not removed[student] and left[student] == 0),
    0,
)
answer = []
while head:
    answer.append(head)
    head = right[head]

print(*answer)

复杂度

• 时间复杂度：$O(N+M)$，每次插入和删除都是 $O(1)$
• 空间复杂度：$O(N)$

总结

当题目有以下特征时，考虑双向链表：

1. 需要在序列的任意位置插入/删除元素
2. 能通过编号/指针直接定位要操作的位置
3. 不需要随机访问（按下标查找）

本题所有操作都是按编号进行的，排序后的顺序也不需要随机访问，因此双向链表是天然的最优解。