Description

一天Murphyc从睡梦中醒来，发现自己居然穿越到了弹丸论破的世界。作为原作全成就通关的超高校级Gamer，Murphyc很清楚接下来会发生什么。为了中止Chiaki即将面临的“学级裁判”，Murphyc溜进了未来机关内部，但是只有持有特定编号的识别卡才能进入机关控制室。

好在，Murphyc其实还有另一重身份----法师学徒！虽然Murphyc手中只有门口警卫的识别卡，但机智的他发现该警卫的识别卡编号只要经过若干次Magic操作便可变为原作CG中某重要角色Chisa的的识别码。

Magic操作：对于i与j位置的两个数字你可以消耗|i-j|的魔力值以交换两个数字的位置。

例如

现在已知警卫的识别码为一个长度为n的整数序列a,ai<=n, Chisa的识别码为长度为n的整数序列b,bi<=n,并且，a、b序列均为[1,n]的全排列之一.为了节约魔力，请问Murphyc至少要消耗多少魔力才能获得Chisa的识别码？

 

Input

第一行一个数字T代表测试的组数(T<=20)

对于每组测试，第一行一个数字n代表序列的长度(n<=2e5)

接下来一行有n个数字a1,a2,a3….an(1<=ai<=n)

接下来一行有n个数字b1,b2,b3…bn(1<=bi<=n)

Output

对于每行输出一个整数

Sample Input

1
4
2 3 4 1
1 3 4 2

Sample Output

3

C++版本一

题解：

本题改编自Codeforces Round #324 (Div. 2)

http://codeforces.com/contest/584/problem/E

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200005],b[200005];
int conv[200005];
int main()
{
    freopen("stdin.txt","r",stdin);
    freopen("stdout.txt","w",stdout);
    int zu;
    scanf("%d",&zu);
    while(zu--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),conv[a[i]]=i;
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);
        ll ans=0;
        for(int i=1;i<=n;i++) ans+=abs(i-conv[b[i]]);
        printf("%lld\n",ans/2);
    }
}

C++版本二

题解：

类似题解一

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=2e5+100;
int t,n,m;
int a[N],b[N],c[N],w[N];
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
             scanf("%d",&a[i]);
                w[a[i]]=i;
     
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            c[i]=w[b[i]];
     
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            if(i>c[i])
                sum+=i-c[i];
        }
        cout << sum << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}