ARC088C Papple Sort

题意 : 给定一个只有小写字母的字符串 ，求使得字符串变为回文所需的最小相邻交换次数，或指出无解。

，时限 。

---

若各个字符中，有 个出现次数为奇数，则无解。

回文串相当于指定某些字符应两两配对，然后将它们移到对称的位置。

最小相邻交换次数是经典问题，如果我们知道每个元素的目标位置，通过计算逆序对就可以得到答案。

• 如何配对

对于一个出现偶数次的字符，记出现位置为 。

由于我们不会交换两个相邻相同的字符（显然不优），于是，肯定是 与 配对。

对于出现奇数次（ ）的字符，则是 与 匹配对， 作为整个回文串的中心。

的目标位置已经确定，下文不再考虑。

• 如何给每个对子确定目标位置

考虑任意两个对子 A,B 之间的贡献。

它们原来的位置可能形如：

• A...A...B...B

  我们让 A 在 B 外面，目标状态为 A...B...B...A，则 A,B 之间的交换（逆序对）是 个。

  若 B 在 A 外面，交换也是 个，没有区别。

• A...B...B...A

  此时让 A 在 B 外面，则无需交换，否则会产生 个交换。

综上，我们让左端点靠左的对子在外面是最优的。

然后使用树状数组求解逆序对，即可做到 。