CF1647E Madoka and the Sixth-graders

在与五年级学生取得了最惊人的成功后，Madoka 被委以教导六年级学生的重任。 她的教室里有 $n$ 张单人课桌。一开始，Madoka 决定让编号为 $b_i$（$1 \le b_i \le n$）的学生坐在第 $i$ 张课桌上。此外，门外还排着一条无限长的学生队伍，编号为 $n+1, n+2, n+3, \ldots$，他们都希望能从 Madoka 本人那里学到些什么。请注意，每个学生都有唯一的编号。 每节课结束后，会依次发生以下事件： 1. 坐在第 $i$ 张课桌的学生会移动到第 $p_i$ 张课桌。所有学生同时移动。 2. 如果某张课桌上有多名学生，则编号最小的学生留下，其余的学生将被永远逐出教室。 3. 对于所有空着的课桌，按编号从小到大顺序，由门外队伍中编号最小的学生依次入座。 注意，最终每张课桌上仍然恰好有一名学生。保证 $p$ 数组中至少有两个元素相同，因此每节课后至少会有一名学生被逐出。可以参考第一个样例的解释以更好地理解过程。 经过若干（可能为零）节课后，第 $i$ 张课桌上坐着编号为 $a_i$ 的学生。给定 $a_1, a_2, \ldots, a_n$ 和 $p_1, p_2, \ldots, p_n$，请你找出字典序最小的、可能的初始座位排列 $b_1, b_2, \ldots, b_n$。 排列是 $n$ 个 $1$ 到 $n$ 的不同整数的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但数组中有 $4$）。 对于两个长度相同的不同排列 $a$ 和 $b$，如果在第一个不同的位置，$a$ 的元素小于 $b$ 的对应元素，则 $a$ 的字典序小于 $b$。

输入的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示教室中的课桌数量。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示学生们将要移动到的课桌编号。保证 $p$ 数组中至少有两个元素相同。 第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示最终每张课桌上的学生编号。保证存在某个初始排列可以得到最终的 $a$。

输出一行 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le n$），表示能够得到最终座位 $a$ 的、字典序最小的初始六年级学生座位排列。

第一个测试样例的说明如下：  第一张图展示了初始排列，即答案。然后，坐在第 $1, 2$ 号课桌的学生都移动到了第 $5$ 号课桌。同时，原本坐在第 $5$ 号课桌的学生移动到了第 $1$ 号课桌，原本坐在第 $4$ 号课桌的学生移动到了第 $3$ 号课桌。 因此，经过这些移动后，得到了第二张图所示的排列。接着，在第 $5$ 号课桌上，编号为 $3$ 的学生被逐出，在第 $3$ 号课桌上，编号为 $5$ 的学生被逐出（因为他们的编号不是最小的）。然后，编号为 $6, 7$ 的新学生分别坐到了第 $2, 4$ 号课桌上。第三张图展示了第一节课结束后的排列。 第四张图展示了第二节课后、所有多余学生被逐出之前的座位情况。第五张图展示了第二节课结束后的最终座位。 由 ChatGPT 4.1 翻译