The Forbidden Permutation

题意翻译

给定 $3$ 个整数 $n,m,d$、一个 $n$ 的排列 $p$ 和一个长度为 $m$ 的数组 $a$，定义 $\mathrm{pos}(x)$ 为 $p$ 中 $x$ 的下标。 数组 $a$ 是不好的，当且仅当对于所有 $1\le i<m$，有 $\mathrm{pos}(a_i)<\mathrm{pos}(a_{i+1})\le\mathrm{pos}(a_i)+d$。 每一次操作，你可以选择 $p$ 中的两个相邻数字并把它们交换，求最小的操作次数，使得 $a$ 变为好的。 by @zfx1569_HCl_2023

题目描述

You are given a permutation $ p $ of length $ n $ , an array of $ m $ distinct integers $ a_1, a_2, \ldots, a_m $ ( $ 1 \le a_i \le n $ ), and an integer $ d $ . Let $ \mathrm{pos}(x) $ be the index of $ x $ in the permutation $ p $ . The array $ a $ is not good if - $ \mathrm{pos}(a_{i}) < \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d $ for all $ 1 \le i < m $ . For example, with the permutation $ p = [4, 2, 1, 3, 6, 5] $ and $ d = 2 $ : - $ a = [2, 3, 6] $ is a not good array. - $ a = [2, 6, 5] $ is good because $ \mathrm{pos}(a_1) = 2 $ , $ \mathrm{pos}(a_2) = 5 $ , so the condition $ \mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d $ is not satisfied. - $ a = [1, 6, 3] $ is good because $ \mathrm{pos}(a_2) = 5 $ , $ \mathrm{pos}(a_3) = 4 $ , so the condition $ \mathrm{pos}(a_2) < \mathrm{pos}(a_3) $ is not satisfied. In one move, you can swap two adjacent elements of the permutation $ p $ . What is the minimum number of moves needed such that the array $ a $ becomes good? It can be shown that there always exists a sequence of moves so that the array $ a $ becomes good. A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array) and $ [1,3,4] $ is also not a permutation ( $ n=3 $ , but there is $ 4 $ in the array).

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ m $ and $ d $ ( $ 2\leq n \leq 10^5 $ , $ 2\leq m\leq n $ , $ 1 \le d \le n $ ), the length of the permutation $ p $ , the length of the array $ a $ and the value of $ d $ . The second line contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1\leq p_i \leq n $ , $ p_i \ne p_j $ for $ i \ne j $ ). The third line contains $ m $ distinct integers $ a_1, a_2, \ldots, a_m $ ( $ 1\leq a_i \leq n $ , $ a_i \ne a_j $ for $ i \ne j $ ). The sum of $ n $ over all test cases doesn't exceed $ 5 \cdot 10^5 $ .

输出格式

For each test case, print the minimum number of moves needed such that the array $ a $ becomes good.

输入输出样例

输入样例 #1

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

输出样例 #1

1
3
2
0
2

说明

In the first case, $ pos(a_1)=1 $ , $ pos(a_2)=3 $ . To make the array good, one way is to swap $ p_3 $ and $ p_4 $ . After that, the array $ a $ will be good because the condition $ \mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d $ won't be satisfied. In the second case, $ pos(a_1)=1 $ , $ pos(a_2)=4 $ . The $ 3 $ moves could be: 1. Swap $ p_3 $ and $ p_4 $ . 2. Swap $ p_2 $ and $ p_3 $ . 3. Swap $ p_1 $ and $ p_2 $ . After these moves, the permutation $ p $ will be $ [2,5,4,3,1] $ . The array $ a $ will be good because the condition $ \mathrm{pos}(a_1) < \mathrm{pos}(a_2) $ won't be satisfied. It can be shown that you can't make the array $ a $ good with fewer moves.In the third case, $ pos(a_1)=1 $ , $ pos(a_2)=3 $ , $ pos(a_3)=5 $ . The $ 2 $ moves can be: 1. Swap $ p_4 $ and $ p_5 $ . 2. Swap $ p_3 $ and $ p_4 $ . After these moves, the permutation $ p $ will be $ [3,4,2,1,5] $ . The array $ a $ will be good because the condition $ \mathrm{pos}(a_2) < \mathrm{pos}(a_3) $ won't be satisfied. It can be shown that you can't make the array $ a $ good with fewer moves.In the fourth case, $ pos(a_1)=2 $ , $ pos(a_2)=1 $ . The array $ a $ is already good. In the fifth case, $ pos(a_1)=2 $ , $ pos(a_2)=5 $ . The $ 2 $ moves are: 1. Swap $ p_1 $ and $ p_2 $ . 2. Swap $ p_5 $ and $ p_6 $ .

**题意翻译**

给定3个整数$n, m, d$、一个$n$的排列$p$和一个长度为$m$的数组$a$，定义$\mathrm{pos}(x)$为$p$中$x$的下标。

数组$a$是不好 的，当且仅当对于所有$1\le i
每一次操作，你可以选择$p$中的两个相邻数字并把它们交换，求最小的操作次数，使得$a$变为好的。

**题目描述**

给定一个长度为$n$的排列$p$，一个包含$m$个不同整数的数组$a_1, a_2, \ldots, a_m$（$1 \le a_i \le n$），和一个整数$d$。

令$\mathrm{pos}(x)$为$x$在排列$p$中的下标。如果对于所有$1 \le i < m$，满足$\mathrm{pos}(a_i)<\mathrm{pos}(a_{i+1})\le\mathrm{pos}(a_i)+d$，则数组$a$是不好的。

例如，对于排列$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$变为好的。

**输入输出格式**

**输入格式**

每个测试包含多个测试用例。第一行包含测试用例数$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$变为好的最小操作次数。

**输入输出样例**

**输入样例 #1**

```
5
4 2 2
1 2 3 4
1 3
5 2 4
5 4 3 2 1
5 2
5 3 3
3 4 1 5 2
3 1 2
2 2 1
1 2
2 1
6 2 4
1 2 3 4 5 6
2 5
```

**输出样例 #1**

```
1
3
2
0
2
```

**说明**

在第一个案例中，$\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$。3个操作可以是：

1. 交换$p_3$和$p_4$。
**题意翻译** 给定3个整数$n, m, d$、一个$n$的排列$p$和一个长度为$m$的数组$a$，定义$\mathrm{pos}(x)$为$p$中$x$的下标。 数组$a$是不好 的，当且仅当对于所有$1\le i