这道题当时CF打了，赛后得知有一种非常精妙的写法，因为他是要把字母倒过来问我们要走几步，那么就给每个字母倒过来赋个值，然后在交换顺序后把值放进去做一个逆序对就可以了
下附代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<vector> 4 #define ll long long 5 using namespace std; 6 vector<int> cnt[30]; 7 int a[200005],b[200005]; 8 char s[200005]; 9 ll res=0; 10 void merge(int l,int r){ 11 if (l==r) return ; 12 int mid=(l+r)>>1; 13 merge(l,mid); 14 merge(mid+1,r); 15 int k=0,i=l,j=mid+1; 16 while (i<=mid && j<=r){ 17 if (a[i]<=a[j]) b[++k]=a[i++]; 18 else b[++k]=a[j++],res+=mid-i+1; 19 } 20 while (i<=mid) b[++k]=a[i++]; 21 while (j<=r) b[++k]=a[j++]; 22 for (int i=l,j=1; i<=r; ++i,++j) a[i]=b[j]; 23 } 24 int main(){ 25 int n; 26 scanf("%d",&n); 27 scanf("%s",s+1); 28 for (int i=n; i>=1; i--){ 29 cnt[s[i]-'a'].push_back(i); 30 } 31 for (int i=1; i<=n/2; i++) 32 swap(s[i],s[n-i+1]); 33 for (int i=1; i<=n; i++){ 34 a[i]=cnt[s[i]-'a'].back(),cnt[s[i]-'a'].pop_back(); 35 } 36 res=0; 37 merge(1,n); 38 printf("%lld",res); 39 }