Cod sursa(job #2569163)

Utilizator NashikAndrei Feodorov Nashik Data 4 martie 2020 11:21:07
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.51 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("litere.in");
ofstream cout("litere.out");
int aib[30],n;
char ch;
void upd(int a,int val){
    for(;a<=26;a+=(a&(-a))){
        aib[a]+=val;
    }
}
long long que(int a){
    long long sol=0;
    for(;a>=1;a-=(a&(-a))){
        sol+=aib[a];
    }
    return sol;
}
int main()
{
    long long sol=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ch;
        sol+=i-que(ch-'a'+1)-1;
        upd(ch-'a'+1,1);
    }
    cout<<sol;
    return 0;
}