问题 5198 --圣诞礼物

5198: 圣诞礼物★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 42  解决: 17
[提交][状态][命题人:]

题目描述

圣诞节到了,圣诞老人要给孩子们送礼物。圣诞老人共准备了n件礼物,为了更好地完成礼物的派送,圣诞老人对这些礼物依次编号为123……n,并将其一次放入一个高高的箱子中,嗯嗯,箱子很高,并且每一层只能放一件礼物,最上面的礼物的编号为a1,下一个的编号为a2,以此类推,最下面的礼物的编号为an(类似栈的概念)。很显然,ai不等于aj(当i不等于j时),且1<=ai,aj<=n

为了有序地给孩子们发放礼物,圣诞老人拟定了一份礼物清单为b1, b2……bm,显然,bi不等于bj(当i不等于j时),且1<=bi,bj<=n。他将按b1, b2……bm的顺序依次发放礼物。

要发送礼物,圣诞老人必须从礼物箱子中找到它。为了拿到编号为t的礼物,圣诞老人首先需要移除t上面所有的礼物,然后拿走编号为t的礼物,最后将所有移除的礼物再重新放回箱子中。我们都知道,圣诞老人的能力很强,他可以1秒钟从箱子中拿出一件礼物或者将一件礼物放回箱子中。所以,如果圣诞老人想要送的礼物上面有k件礼物,他需要2k+1秒才能送完。幸运的是,圣诞老人可以加快整个过程:当他把礼物重新放回箱子中时,他可以按照自己的意愿重新排列它们(只有那些在礼物t的上面的礼物可以重排,因为这些需要重新放回箱子里,t下面的礼物不会受到任何影响)

    如果圣诞老人知道他要送的礼物清单,并以最佳方式重新排列,那么发送所有礼物所需的最短时间是多少

输入

第一行包含一个整数s (1≤s≤100):表示测试样例的数量。

接下来是s组测试样例,每组测试样例共三行:

第一行包含两个整数nm(1≤m≤n≤105),分别是圣诞老人所准备的礼物数量和圣诞老人想要发送的礼物数量。

第二行包含n个整数a1, a2 an(1≤ai≤n,所有ai都是唯一的):礼物在箱子中的顺序,a1在最上面,a2a1的下面,依次类推……an在最下面。

第三行包含m个整数b1, b2 bm(1≤bi≤n,所有bi都是唯一的):圣诞老人要送的礼物的列表。

所有测试用例的n之和不超过105

输出

对于每组测试样例,输出一个整数:如果圣诞老人每次将礼物放回箱子时以最佳方式重新排序,那么他必须花费在发送礼物上的最小秒数。

样例输入
Copy
2
3 3
3 1 2
3 2 1
7 2
2 1 7 3 4 5 6
3 1
样例输出
Copy
5
8

提示

对于第一组测试样例,发放3号礼物只需要1秒,发放礼物2需要3秒,发放礼物1需要1秒,共5秒。

对于第二组测试样例,发放3号礼物需要7秒,因为首先需要将3号礼物上面的3件礼物(2号、1号和7号礼物)取出来,再拿出3号礼物,再将3件礼物放回去。发放1号礼物只需要1秒,因为在将3将礼物放回箱子时,可以将1号礼物放在最上面。因此,圣诞老人派送礼物的时间共8秒。

来源

[提交][状态]