Codeworks educational round 96 [reverse pair] E. string reverse

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;
}

Read More: