CodeForces - 1430E（逆序对、思维）
90nwyn
2020-11-27 22:47:04
[题目链接](https://vjudge.net/problem/CodeForces-1430E)
------------
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
typedef long long ll;
const int M=2e5+5;
int n,a[M],c[M];
char s[M];
ll ans;
queue<int> q[M];
void upd(int i){for(;i<=n;i+=lowbit(i))c[i]++;}
int que(int i){int y=0;for(;i;i-=lowbit(i))y+=c[i];return y;}
int main()
{
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++)
{
int d=s[i]-'a'+1;
q[d].push(i);
}
for(int i=n;i>=1;i--)
{
int d=s[i]-'a'+1;
a[n-i+1]=q[d].front();
q[d].pop();
}
for(int i=1;i<=n;i++)
{
upd(a[i]);
ans+=i-que(a[i]);
}
printf("%lld\n",ans);
return 0;
}
```