[CF1365F] Swaps Again

Description

给定两个长度为 (n) 的数组 (a,b)，每次操作可以选择一个 (k)，交换 (a) 中的长度为 (k) 的后缀与长度为 (k) 的前缀。求是否能通过若干次操作使得 (a,b) 完全相同。

Solution

观察到任意操作中，所有无序对 ((a_i,a_{n-i+1})) 构成的集合是不变的。并且我们可以通过多次操作来实现对任意一对 (a_i,a_{n-i+1}) 的对调，或是对无序对 ((a_i,a_{n-i+1})),((a_j,a_{n-j+1})) 的位置互换。

因此，只需要判断所有无序对 ((a_i,a_{n-i+1})) 构成的集合是否相等即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int a[N],b[N],n,t;

bool solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    multiset <pair<int,int>> s,t;
    for(int i=1;i<=n/2;i++) s.insert({min(a[i],a[n-i+1]),max(a[i],a[n-i+1])});
    for(int i=1;i<=n/2;i++) t.insert({min(b[i],b[n-i+1]),max(b[i],b[n-i+1])});

    if(n&1)
    {
        if(a[(n+1)/2]!=b[(n+1)/2]) return false;
    }

    for(auto its=s.begin(), itt=t.begin(); its!=s.end() && itt!=t.end(); its++, itt++)
    {
        if(*its!=*itt) return false;
    }

    return true;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin>>t;
    while(t--)
    {
        if(solve())
        {
            puts("Yes");
        }
        else 
        {
            puts("No");
        }
    }
}