Pagini recente » Cod sursa (job #819951) | Cod sursa (job #1089726) | Cod sursa (job #2005383) | Cod sursa (job #2419798) | Cod sursa (job #1899985)
#include<bits/stdc++.h>
#define lsb(i) (i&(-i))
using namespace std;
int AIB[30],n,inv;
char c;
void update(int pos,int x)
{
for(int i=pos;i<=26;i+=lsb(i))
{
AIB[i]+=x;
}
}
int query(int pos)
{
int sum=0;
for(int i=pos;i>=1;i-=lsb(i))
{
sum+=AIB[i];
}
return sum;
}
int main()
{
freopen("litere.in","r",stdin);
freopen("litere.out","w",stdout);
scanf("%d",&n);
scanf("\n");
for(int i=0;i<n;i++)
{
scanf("%c",&c);
int q=query(26)-query(c-'a'+1);
inv+=q;
update(c-'a'+1,1);
}
printf("%d\n",inv);
return 0;
}