题 目 链 接

这个题和前几天那场的c类似：（这个感觉比上一题简单啊...）
链接：https://codeforces.com/contest/1670/problem/C

前几天是找环，然后计数；
这个题是找环，然后贪心赋值就行；（一个最大，一个最小）

我焯，有坑！！！收回上面的话...
题解：https://zhuanlan.zhihu.com/p/511388683

当这个环是奇数的时候，最后一个点赋什么值并不影响这个环答案的贡献；
所以我们干脆就别赋值，留着最大值和最小值...

所以我们还要看一下当前环是不是奇数...

这种《置换环》好难敲啊...
主要是看题解也看不太懂...只能自己模拟找环...

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<cmath> 
#include<algorithm>
#include<deque>
#include<stack>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;

#define pb push_back
#define coutt cout<<"------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;

const int maxn = 1e5 + 7;
const int N = 2e5+7;
const int M = 1e6+7;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 3.14159265359;

ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}

int a[maxn];
int b[maxn];
int posa[maxn];
int posb[maxn];

int vis[maxn];

void solve()
{
    int n; scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]), posa[a[i]] = i, vis[i] = 0;
    for(int i=1;i<=n;i++) scanf("%d",&b[i]), posb[b[i]] = i;

    int l = 1;
    int r = n;

    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i] == 1) continue;
        if(a[i] == b[i]) continue;

        vector<int> v;  //存环

        int p = i;
        while(!vis[p])  //找环
        {
            vis[p] = 1;

            v.push_back(a[p]);
            v.push_back(b[p]);

            p = posa[b[p]];
        }

        if((v.size() / 2) & 1)  //奇数环
        {
            //删掉最后一个点
            v[v.size() - 3] = v[v.size() - 1];
            v.erase(v.end()-1);
            v.erase(v.end()-1);
        }

        int f = 1;
        int num = r;    //终点 起点 的值
        //计算答案
        for(int j=1;j<v.size();j++)
        {
            if(v[j] == v[j-1]) continue;

            if(j == v.size()-1) //跑到终点了
            {
                ans += (num-l);
                l++;
                continue;
            }

            ans += (r-l);

            if(f == 1) r--;
            else l++;

            f *= -1;
        }
    }

    cout<<ans<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}