[??记录]AT3733 [ARC088C] Papple Sort

**题意** : 给定一个只有小写字母的字符串 $S$ ，求使得字符串变为回文所需的最小相邻交换次数，或指出无解。 $|S|\leq 2\times 10^5$ ，时限$\texttt{2s}$。 ------------ 若各个字符中，有 $\geq 2$ 个出现次数为奇数，则无解。 回文串相当于指定某些字符应两两配对，然后将它们移到对称的位置。 最小相邻交换次数是经典问题，如果我们知道每个元素的目标位置，通过计算逆序对就可以得到答案。 - **如何配对** 对于一个出现偶数次的字符，记出现位置为 $i_1,i_2,...,i_{2m}$。 由于我们不会交换两个相邻相同的字符（显然不优），于是，肯定是 $i_k$ 与 $i_{2m-k+1}$ 配对。 对于出现奇数（ $2m+1$ ）次的字符，则是 $i_k$ 与 $i^{2m-k+2}$ 匹配对， $i_m$ 作为整个回文串的中心。 $i_m$ 的目标位置已经确定，下文不再考虑。 - **如何给每个对子确定目标位置** 考虑任意两个对子 `A,B` 之间的贡献。 它们原来的位置可能形如 ： - `A...A...B...B` 我们让 `A` 在 `B` 外面，目标状态为 `A...B...B...A` ，则 `A,B` 之间的交换（逆序对）是 $2$ 个。 若 `B` 在 `A` 外面，交换也是 $2$ 个，没有区别。 - `A...B...B...A` 此时让 `A` 在 `B` 外面，则无需交换，否则会产生 $2$ 个交换。 综上，我们让左端点靠左的对子在外面是最优的。 然后使用树状数组求解逆序对，即可做到 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #define Pr pair<int,int> #define fir first #define sec second #define mp make_pair #define ll long long #define MaxN 200500 using namespace std; int o[MaxN],n; #define lbit(x) (x&-x) void add(int p) {while(p<=n){o[p]++;p+=lbit(p);}} int qry(int p){ int ret=0; while(p){ret+=o[p];p^=lbit(p);} return ret; } Pr t[MaxN]; int tn,sp[MaxN]; char s[MaxN]; vector<int> p[26]; int main() { scanf("%s",s+1);n=strlen(s+1); for (int i=1;i<=n;i++) p[s[i]-'a'].push_back(i); int cnt=0; for (int c=0;c<26;c++)cnt+=p[c].size()&1; if (cnt>1){puts("-1");return 0;} for (int c=0;c<26;c++){ for (int i=0;i<p[c].size()/2;i++) t[++tn]=mp(p[c][i],p[c][p[c].size()-i-1]); if (p[c].size()&1)sp[p[c][p[c].size()/2]]=(n+1)/2; }sort(t+1,t+tn+1); for (int i=1;i<=tn;i++){ sp[t[i].fir]=i;sp[t[i].sec]=n-i+1; } ll ans=0; for (int i=1;i<=n;i++){ add(sp[i]); ans+=i-qry(sp[i]); }printf("%lld",ans); return 0; } ```