[CF1430E] String Reversal

Description

给定一个字符串 (s)，求至少对 (s) 进行多少次相邻字符交换操作才能使得 (s) 变成 (s) 的翻转串。

Solution

如果将整个交换过程看做一个置换，显然最少的相邻交换次数等于置换的逆序对个数。

那么我们将同一种字符在正序和倒序串中的出现位置都记录下来，然后顺序匹配即可。

这样就可以算出一个排列，我们只需要计算这个排列的逆序对数即可。求逆序对数直接树状数组即可，倒序扫描整个置换，把这个数后面比它小的数的数目加入答案即可。

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

#define int long long 
const int M = 205;
int n;
string str;

struct BinaryIndexTree 
{
    int size;
    vector <int> a;

    BinaryIndexTree(int n)
    {
        size=n;
        a.resize(n+2);
    }

    int lowbit(int x)
    {
        return x&(-x);
    }

    void Add(int i)
    {
        while(i<=size)
        {
            a[i]++;
            i+=lowbit(i);
        }
    }

    int sum(int i)
    {
        int ans=0;
        while(i>0)
        {
            ans+=a[i];
            i-=lowbit(i);
        }
        return ans;
    }

    int Sum(int l,int r)
    {
        return sum(r)-sum(l-1);
    }
};

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>str;


    vector <int> vec_pos_seq[M],vec_pos_rev[M];

    for(int i=0;i<str.length();i++)
    {
        vec_pos_seq[str[i]].push_back(i);
        vec_pos_rev[str[i]].push_back(str.length()-i-1);
    }

    for(char c='a';c<='z';c++)
    {
        sort(vec_pos_seq[c].begin(),vec_pos_seq[c].end());
        sort(vec_pos_rev[c].begin(),vec_pos_rev[c].end());
    }
    vector <int> p(n+2);

    for(char c='a';c<='z';c++)
    {
        int tot=vec_pos_seq[c].size();
        for(int i=0;i<tot;i++)
        {
            p[vec_pos_seq[c][i]+1]=vec_pos_rev[c][i]+1;
        }
    }


    int ans=0;
    BinaryIndexTree bit(n);
    for(int i=n;i>=1;i--)
    {
        ans+=bit.Sum(1,p[i]);
        bit.Add(p[i]);
    }

    cout<<ans<<endl;
}