CF2086C.Disappearing Permutation

一个从 $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}$ 都会变为 $0$。

在每次查询后，你需要找到修复数组所需的最少操作次数；换句话说，将当前数组转换为从 $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}$ 被替换为 $0$ 后）修复数组所需的最少操作次数。

• 在第一个测试用例中，每次查询后，每个被替换为 $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}]$。

标红的数字表示被修改的元素。

翻译由 DeepSeek V3 完成