题目大意

给定一个长度为 $n$ 的数列 $a$，要求求出一个排列 $p$ 满足 $a_{p_1},a_{p_2},\cdots ,a_{p_n}$ 是一个回文字符串而且把 $i$ 向 $p_i$ 连边得到的图中只有一个环。

数据范围满足，$1\le \sum n\le 2\times10^5$。

思路

先不考虑 $p$ 是否构成满足要求的环，这样这个题目就很简单了。在构造出了满足 $a_{p_1},a_{p_2},\cdots ,a_{p_n}$ 是回文串的 $p$ 数组之后，考虑哪些 $p$ 中的位置是可以交换的。

1. 如果 $a_{p_i}=a_{p_j}$，那么 $p_i$ 与 $p_j$ 是可以交换的。
2. 可以同时交换 $p_i,p_j$ 和 $p_{n-i+1},p_{n-j+1}$，这样原串的回文性质依旧满足。

在连出的图中，考虑怎么将多个环通过合法的交换合并。

对于下面的这种情况，我们可以在 $a_{p_i}=a_{p_j}$ 的情况下交换 $p_i,p_j$ 将两个环合并。

交换 $p_i,p_j$ 得到：

可以看到这样这两个环就合并了。

但是仅仅合并 $a_{p_i}=a_{p_j}$ 的情况不可以合并所有的环，所以考虑将 $p_i,p_j$ 和 $p_{n-i+1},p_{n-j+1}$ 同时交换。

对于下图这种情况：

先交换 $p_i,p_j$ 和 $p_{n-i+1},p_{n-j+1}$，得到：

再交换 $p_i$ 和 $p_{n-i+1}$，因为 $a$ 序列已经是一个回文串了，所以 $a_{p_i}$ 与 $a_{p_{n-i+1}}$ 注定是一样的。

因为通过第一种合并，我们将所有的 $a_{p_i}$ 的值一样的点全部都到了一个环里，所以在第二个操作中注定可以将能合并的全部合并。

对于具体的实现，考虑使用并查集维护一下是否在一个环中，接着模拟即可。

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int N=2e5+5;
int n,p[N];
struct node{int x,p,id;}a[N];
bool cmp(node a,node b){return a.x<b.x;}bool cmp1(node a,node b){return a.id<b.id;}
map<int,int>mp;
struct CJH{
    int fa[N];void clear(){for(int i=1;i<=n;i++)fa[i]=i;}
    int find_root(int x){return fa[x]==x?x:fa[x]=find_root(fa[x]);}
    int ask(int x,int y){return find_root(x)==find_root(y);}
    void add(int x,int y){fa[find_root(x)]=find_root(y);}
}dsu;
vector<int> v[N];
void solve(){
    cin>>n;
    dsu.clear(),mp.clear();
    for(int i=1;i<=n;i++){
        cin>>a[i].x,a[i].id=i;
        mp[a[i].x]++,v[i].clear();
    }
    int cnt=0;
    for(auto i:mp) if(i.second&1) cnt++;
    if(cnt>1||cnt==1&&n%2==0){cout<<"NO\n";return;}
    int tot=0;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(i<n&&a[i].x==a[i+1].x) p[++tot]=a[i].id,p[n-tot+1]=a[++i].id;
        else p[(n+1)/2]=a[i].id;
    }
    sort(a+1,a+1+n,cmp1);
	for(int k=1;k<=n;k++) a[k].p=p[k];
    mp.clear(),tot=0;
    for(int i=1;i<=n;i++) if(!mp[a[i].x]) mp[a[i].x]=++tot;
    for(int i=1;i<=n;i++){
        dsu.add(i,a[i].p);
        v[mp[a[a[i].p].x]].push_back(i);
    }
    for(int i=1;i<=tot;i++){
        for(int j=1;j<v[i].size();j++){
            if(!dsu.ask(v[i][0],v[i][j])){
                swap(a[v[i][0]].p,a[v[i][j]].p);
                dsu.add(v[i][0],v[i][j]);
            }
        }
    }
    for(int i=2;i<n-i+1;i++){
        if(!dsu.ask(1,i)){
            dsu.add(1,i);
            swap(a[1].p,a[i].p);
            swap(a[n].p,a[n+1-i].p);
            swap(a[1].p,a[n].p);
        }
    }
    for(int i=2;i<=n;i++){if(!dsu.ask(1,i)){cout<<"NO\n";return;}}
    cout<<"YES\n";for(int i=1;i<=n;i++) cout<<a[i].p<<' ';cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}