题目
给定字符串，问最少多少次交换相邻字母能变成回文串。
分析
贪心，对每个字母计算首个和最后一个移到端点的次数，可以用树状数组维护，
可以发现每次选取移动次数最少的字母就是最优的，可以通过两个字母位置间的分类讨论证明
那么选完字母之后用双端队列把字母对应的开头结尾位置删除即可。
代码
#include <iostream>
#include <string>
#include <deque>
using namespace std;
const int N=1000011; deque<int>q[26];
int n,odd,c[N]; long long Ans; string str;
void del(int x){for (;x<=n;x+=-x&x) --c[x];}
int query(int x){int ans=0; for (;x;x-=-x&x) ans+=c[x]; return ans;}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>str,n=str.length();for (int i=0;i<n;++i) q[str[i]-'A'].push_back(i+1),c[i+1]=-(i+1)&(i+1);for (int i=0;i<26;++i) if (q[i].size()&1) ++odd;if (odd>(n&1)){cout<<-1;return 0;}for (int i=1;i<=n/2;++i){int pos=-1,ans=0x3f3f3f3f;for (int j=0;j<26;++j)if (q[j].size()>1){int now=query(q[j].front()-1)+(n-i*2)-query(q[j].back());if (ans>now) ans=now,pos=j;}del(q[pos].front()),del(q[pos].back()),Ans+=ans;q[pos].pop_front(),q[pos].pop_back();}cout<<Ans;return 0;
}