Cod sursa(job #1899985)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 3 martie 2017 08:28:29
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#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;
}