← 返回题目列表

Codeforces · 2086/C

C. 消失排列

中文机器翻译题面 查看原题

从 $$$1$$$ 到 $$$n$$$ 的整数排列是一个大小为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。

给你一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p$$$。您必须处理 $$$n$$$ 查询。在第 $$$i$$$ 查询期间,您将 $$$p_{d_i}$$$ 替换为 $$$0$$$。每个元素都被 $$$0$$$ 替换一次。查询中所做的更改将被保存,即在第 $$$i$$$ 次查询之后,所有整数 $$$p_{d_1}、p_{d_2}、\dots、p_{d_i}$$$ 均为零。

每次查询后,您必须找到完成该操作所需的最少操作数 修复 数组;换句话说,将当前数组转换为从 $$$1$$$ 到 $$$n$$$ 的任何整数排列(可能转换为原始排列 $$$p$$$,也可能转换为其他排列)。

您可以执行以下操作来修复阵列:

  • 从$$$1$$$到$$$n$$$中选择整数$$$i$$$,替换数组的第$$$i$$$个元素 与 $$$i$$$.

请注意,每个查询的答案都是独立计算的,这意味着您实际上并不应用任何操作,只是计算最小操作数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。然后是测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{5}$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_{i} \le n$$$) - 原始排列。所有 $$$p_i$$$ 都是不同的。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_{i} \le n$$$)。所有 $$$d_{i}$$$ 都是不同的。

输入的附加约束:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,输出一行包含 $$$n$$$ 整数,其中第 $$$i$$$ 个整数应等于修复第 $$$i$$$ 个查询后获得的数组所需的最小操作数(即排列 $$$p$$$,其中所有整数 $$$p_{d_1}、p_{d_2}、\dots、 p_{d_i}$$$ 被零替换)。

示例

输入
复制

3
3
1 2 3
3 2 1
5
4 5 3 1 2
4 5 1 3 2
7
4 3 1 2 7 5 6
1 2 3 4 5 6 7

输出
复制

1 2 3 
2 4 4 5 5 
4 4 4 4 7 7 7 

注意

在第一个测试用例中,每次查询后,每个被 $$$0$$$ 替换的整数都可以通过一次操作恢复。

在第二个测试用例中,您可以执行以下操作:

  • 查询$$$1$$$:$$$p = [4, 5, 3, 0, 2]$$$,可转化为$$$[{\color{red}1}, 5, 3, {\color{red}4}, 2]$$$。
  • 查询$$$2$$$:$$$p = [4, 5, 3, 0, 0]$$$,可转化为$$$[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$$$。
  • 查询$$$3$$$:$$$p = [0, 5, 3, 0, 0]$$$,可转化为$$$[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$$$。
  • 查询$$$4$$$:$$$p = [0, 5, 0, 0, 0]$$$,可转化为$$$[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$$$。
  • 查询$$$5$$$:$$$p = [0, 0, 0, 0, 0]$$$,可转化为$$$[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$$$。

已更改的数字以红色突出显示。