swap adjacent positions and the first thing that comes to mind is inversions!
think bubble sort, = reverse exchange for the number of the original string position can be seen as an ordered sequence, such as
a aa z a
1, 2, 3, 4, 5
after reverse sequence is:
a to z a aa
for each location should choose the original series more the front of the plane, so to reverse contribution to the smallest reason should be:
1 2 3 4 5
o problem can be converted to reverse the number!
#include<iostream>
#include<vector>
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 2e5 + 5;
char s[N];
ll n,a[N],b[N];
vector<ll> v[26];
int pos[26];
ll merge(int l,int r){
ll ans = 0;
if(l >= r){
return 0;
}
int mid = (l + r)>>1;
ans += merge(l,mid);
ans += merge(mid + 1,r);
int i = l,j = mid + 1,k = 0;
while(i<=mid && j <= r){
if(a[i] <= a[j]){
b[++k] = a[i++];
ans+= j - mid - 1;
}
else
b[++k] = a[j++];
}
while(i <= mid)b[++k] = a[i++],ans += r - mid;
while(j <= r)b[++k] = a[j++];
for(i = l;i <= r;i++)
a[i] = b[i - l + 1];
return ans;
}
int main(){
cin>>n;
cin>>(s + 1);
for(int i = 1;i <= n;i++)v[s[i] - 'a'].pb(i);
int j = 0;
for(int i = n;i>=1;i--){
a[++j] = v[s[i] - 'a'][pos[s[i] - 'a']++];
}
cout<<merge(1,n)<<endl;
cout<<endl;
return 0;
}