[HAOI2009] 求回文串

Description

给定长度为 n 的字符串 s ，每次只能交换相邻两个位置。求使得 s 为回文串的最小交换次数。无解输出 -1 。
$n\leq 10^6$，保证都是大写字母

Solution

无解的情况判定：讨论 n 的奇偶性以及 s 中各字母的出现次数的奇偶性即可。

对于“每次只能交换相邻两个位置，求最小交换次数”的题目，通常采取的办法为得到目标序列，并定义 las[i] 表示初始序列中的第 i 个数最终应在目标序列的 las[i] 位置上。 las 数组的逆序对数即为答案。

问题转化为求解目标序列。假设我们在处理字母 x 时遇到了下述情况。x 的出现位置为 a,b,c,d 。

$\cdots,a,\cdots,b,\cdots,c,\cdots,d,\cdots$

事实上，我们固定 a b 不变，让 d 去适配 a 的位置，c 去适配 b 的位置一定是最优的。
假设我们让 c 适配 a ，d 适配 b，那么无论如何 c d 都会相遇一次。而 c d 本质上是同一个东西，也就是说相遇之后走的距离完全是多余的。

于是我们得到了适配同一字母的所有的位置的方法。

对于不同的字母呢？考虑下述情况，其中 c d 分别表示 a b 的对称位置。

$\cdots,a,\cdots,b,\cdots,c,\cdots,d,\cdots$

交换 a b 的位置是否可以更优？我们考虑 a 适配的位置为 $p_a$ ，b 适配的位置为 $p_b$ ，显然，当 $p_a\geq d$ , $p_b\leq c$ 时，可以使交换 a b 的位置后减少的步数最大化（单论步数的变换量而言的话，$\geq$ 或者 $\leq$ 与 $=$ 是等效的）。但是，即使是这种情况下（$p_a=d,p_b=c$），交换与否步数也只是恰好相等。故对于两个不同的字母，不交换一定不劣于交换。

综上，我们可以贪心地构造出 las 数组。

Code

if(num==1){
    for(int i=0;i<26;++i) if(d[i]&1){
        int now=p[i][p[i].size()/2];
        las[len+1>>1]=now;vis[now]=1;
    } 
}
int idx=1,nl=1,nr=len;
while(idx<=len&&nl<=nr){
    if(vis[idx]) {++idx;continue;}
    int mat=p[s[idx]].back();
    las[nl]=idx,las[nr]=mat,p[s[idx]].pop_back();
    ++nl,--nr,vis[mat]=1;++idx;
}