题目大意
给定一个长度为 \(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\) 中的位置是可以交换的。
- 如果 \(a_{p_i}=a_{p_j}\)，那么 \(p_i\) 与 \(p_j\) 是可以交换的。
- 可以同时交换 \(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_j}\) 注定是一样的。
因为通过第一种合并，我们将所有的 \(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;
}