CF1778B The Forbidden Permutation

给定一个长度为 $n$ 的排列 $p$，一个包含 $m$ 个互不相同整数的数组 $a_1, a_2, \ldots, a_m$（$1 \le a_i \le n$），以及一个整数 $d$。 记 $\mathrm{pos}(x)$ 表示 $x$ 在排列 $p$ 中的位置。若数组 $a$ 满足以下条件，则称其为“不好”的数组： - 对于所有 $1 \le i < m$，都有 $\mathrm{pos}(a_{i}) < \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d$。 例如，设排列 $p = [4, 2, 1, 3, 6, 5]$，$d = 2$： - $a = [2, 3, 6]$ 是一个不好数组。 - $a = [2, 6, 5]$ 是好数组，因为 $\mathrm{pos}(a_1) = 2$，$\mathrm{pos}(a_2) = 5$，不满足 $\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$。 - $a = [1, 6, 3]$ 是好数组，因为 $\mathrm{pos}(a_2) = 5$，$\mathrm{pos}(a_3) = 4$，不满足 $\mathrm{pos}(a_2) < \mathrm{pos}(a_3)$。 每次操作，你可以交换排列 $p$ 中相邻的两个元素。请问，最少需要多少次操作才能使数组 $a$ 变为好数组？可以证明，总存在一种操作序列使得数组 $a$ 变为好数组。 排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，但数组中有 $4$）。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每组测试用例的第一行包含三个整数 $n$、$m$ 和 $d$（$2\leq n \leq 10^5$，$2\leq m\leq n$，$1 \le d \le n$），分别表示排列 $p$ 的长度、数组 $a$ 的长度和 $d$ 的值。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1\leq p_i \leq n$，$p_i \ne p_j$，$i \ne j$）。 第三行包含 $m$ 个互不相同的整数 $a_1, a_2, \ldots, a_m$（$1\leq a_i \leq n$，$a_i \ne a_j$，$i \ne j$）。 所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出使数组 $a$ 变为好数组所需的最少操作次数。

在第一个样例中，$\mathrm{pos}(a_1)=1$，$\mathrm{pos}(a_2)=3$。为了使数组变为好数组，一种方法是交换 $p_3$ 和 $p_4$。此后，数组 $a$ 就是好数组，因为不再满足 $\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$。 在第二个样例中，$\mathrm{pos}(a_1)=1$，$\mathrm{pos}(a_2)=4$。可以进行如下三步操作： 1. 交换 $p_3$ 和 $p_4$。 2. 交换 $p_2$ 和 $p_3$。 3. 交换 $p_1$ 和 $p_2$。 操作后，排列 $p$ 变为 $[2,5,4,3,1]$。此时数组 $a$ 是好数组，因为不再满足 $\mathrm{pos}(a_1) < \mathrm{pos}(a_2)$。可以证明，无法用更少的操作次数使数组 $a$ 变为好数组。 在第三个样例中，$\mathrm{pos}(a_1)=1$，$\mathrm{pos}(a_2)=3$，$\mathrm{pos}(a_3)=5$。可以进行如下两步操作： 1. 交换 $p_4$ 和 $p_5$。 2. 交换 $p_3$ 和 $p_4$。 操作后，排列 $p$ 变为 $[3,4,2,1,5]$。此时数组 $a$ 是好数组，因为不再满足 $\mathrm{pos}(a_2) < \mathrm{pos}(a_3)$。可以证明，无法用更少的操作次数使数组 $a$ 变为好数组。 在第四个样例中，$\mathrm{pos}(a_1)=2$，$\mathrm{pos}(a_2)=1$。数组 $a$ 已经是好数组。 在第五个样例中，$\mathrm{pos}(a_1)=2$，$\mathrm{pos}(a_2)=5$。可以进行如下两步操作： 1. 交换 $p_1$ 和 $p_2$。 2. 交换 $p_5$ 和 $p_6$。 由 ChatGPT 4.1 翻译