P1160 队列安排

难度： 普及−
标签： 双向链表、数组模拟链表、模拟、数据结构
来源： 洛谷 P1160

题目背景

本题围绕“队列安排”所描述的场景展开。班级中共有 $N$ 名同学，编号为 $1$ 到 $N$。

下面的题面采用非逐字重述方式整理，但保留原题中的全部判定条件、边界含义、输入输出要求与特殊约定。

题目描述

班级中共有 $N$ 名同学，编号为 $1$ 到 $N$。老师按如下过程把他们排成一列：

1. 先让 $1$ 号同学入列，此时队列中只有 $1$ 号；
2. 按编号从 $2$ 到 $N$ 依次安排同学。安排 $i$ 号同学时，老师指定一名已经在队列中的同学 $k$，并要求 $i$ 号站在 $k$ 号的左边或右边；
3. 所有人入列后，再执行 $M$ 条删除指令。每条指令删除指定编号的同学，其他同学的相对顺序保持不变。若该同学之前已经被删除，则忽略本次指令。

完成所有操作后，请输出队列中剩余同学从左到右的编号。

完整规则与任务要求

处理本题时，必须同时满足下列全部要求，不能只实现其中一部分：

• 班级中共有 $N$ 名同学，编号为 $1$ 到 $N$。
• 老师按如下过程把他们排成一列：。
• 1. 先让 $1$ 号同学入列，此时队列中只有 $1$ 号；。
• 2. 按编号从 $2$ 到 $N$ 依次安排同学。
• 安排 $i$ 号同学时，老师指定一名已经在队列中的同学 $k$，并要求 $i$ 号站在 $k$ 号的左边或右边；。
• 3. 所有人入列后，再执行 $M$ 条删除指令。
• 每条指令删除指定编号的同学，其他同学的相对顺序保持不变。
• 若该同学之前已经被删除，则忽略本次指令。
• 同学按编号 $2$ 到 $N$ 依次插入，此时参照同学一定已经在队列中。
• 删除已被删除的同学时忽略该指令。
• 删除后其他同学的相对顺序不能改变。

程序应完整读取“输入格式”中规定的所有数据，并严格按照“输出格式”给出结果。题目中的区间端点、编号起点、排序优先级、同分处理、空结构处理、取模方式和特殊字符串，均以本题面明确写出的规则为准。

所有算法还必须覆盖“数据范围”中的最小规模、最大规模及边界情况，不能只针对样例或小数据。

输入格式

• 第一行输入整数 $N$；
• 接下来共 $N-1$ 行。对每个 $i=2,3,\ldots,N$，输入两个整数 $k,p$，其中 $1\le k<i$：
  • $p=0$ 表示把 $i$ 号同学插到 $k$ 号左边；
  • $p=1$ 表示把 $i$ 号同学插到 $k$ 号右边；
• 下一行输入整数 $M$，表示删除指令数量；
• 接下来 $M$ 行，每行输入一个编号 $x$，表示删除 $x$ 号同学。重复删除同一名同学只在第一次生效。

输出格式

输出一行，按从左到右顺序输出所有未被删除同学的编号，相邻编号之间用空格分隔。

输入输出样例

4
1 0
2 1
1 0
2
3
3

2 4 1

样例说明

• $2$ 号插到 $1$ 号左边：2 1；
• $3$ 号插到 $2$ 号右边：2 3 1；
• $4$ 号插到 $1$ 号左边：2 3 4 1；
• 删除 $3$ 号后得到 2 4 1；
• 再次删除 $3$ 号时，由于他已经不在队列中，本次指令被忽略。

数据范围

• 对于 $20\%$ 的数据：$1\le N\le 10$；
• 对于 $40\%$ 的数据：$1\le N\le 1000$；
• 对于全部数据：$1\le N\le 10^5$，$0\le M\le N$；
• 每次插入时均满足 $1\le k<i$，$p\in\{0,1\}$。

边界与子任务说明

• 测试数据可能覆盖题面允许的最小值、最大值、重复值、空结果、无解或极端结构等边界情形。
• 若原题未额外列出分档子任务，则所有测试点统一遵守上述完整数据范围；若题面已经列出比例或分档条件，则这些条件均应视为题面的一部分。
• 不能根据公开样例推断未写出的额外限制。

本题面依据洛谷 P1160 的公开题目信息重新整理，为内容完整的非逐字重述版。