[HAOI2009] 求回文串

对于任意输入的字符串，不断将第 (i) 个字符和第 (i+1) 个字符交换，使得该串最终变为回文串。求最少交换次数。(n leq 10^6)

Solution

直观的贪心想法：从左向右遍历每个元素，找到序列最右的与它相同的元素，将这两个元素放到目标序列最左、右端然后从原序列中删去，记录下右元素移动的距离就是答案

然而暴力模拟的复杂度为 (O(n^2))，考虑将每种字符的所有出现位置插入一个 vector 中，同时用一个标记数组来维护每个元素是否已经被删去

当我们从左侧找元素的时候，如果遇到了一个没有被标记的元素，就意味着我们找到了一个元素

然后我们通过这个字符的 vector 找到最右侧的相同字符，定位到它的位置，如果这个元素在标记数组中没有被标记，则算找到，否则从 vector 中弹出这个元素并继续找

找到以后计算贡献，并且将这个右侧元素从 vector 中抹掉，左、右两个元素同时在 vector 中标记

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int ar[N]; // index: 1 ~ N
int lowbit(int t) { return t & (-t); }
void add(int i, int v) {
	for (; i < N; ar[i] += v, i += lowbit(i));
}
int sum(int i) {
	int s = 0;
	for (; i > 0; s += ar[i], i -= lowbit(i));
	return s;
}

char str[N];
vector <int> v[26];

int n,ans[N],u[N],tot;

signed main() {
    cin>>str+1;
    n=strlen(str+1);
    for(int i=1;i<=n;i++) v[str[i]-'A'].push_back(i);
    int p1=1, p2=n;
    for(int i=1;i<=n;i++) {
        if(u[i]) continue;
        if(p1>=p2) break;
        while(v[str[i]-'A'].size() && u[v[str[i]-'A'].back()])
            v[str[i]-'A'].pop_back();
        if(v[str[i]-'A'].size()==0) {
            cout<<-1;
            return 0;
        }
        int q=v[str[i]-'A'].back();
        if(q==i) continue;
        u[q]=1;
        v[str[i]-'A'].pop_back();
        u[i]=1;
        tot+=abs(p2-q);
        ans[p1++]=i;
        ans[p2--]=q;
    }
    if(p1==p2) {
        int t=0;
        for(int i=1;i<=n;i++) if(u[i]==0) t=i;
        ans[p1]=t;
        tot+=abs(t-p1);
    }
    tot=0;
    for(int i=1;i<=n;i++) {
        tot+=i-1-sum(ans[i]);
        add(ans[i],1);
    }
    cout<<tot;
}