Pagini recente » Cod sursa (job #3307441) | Borderou de evaluare (job #3248547) | Borderou de evaluare (job #2622327) | Cod sursa (job #893526) | Cod sursa (job #3348313)
#include <fstream>
#include <string>
using namespace std;
ifstream cin("litere.in");
ofstream cout("litere.out");
const int nmax=1e4;
int n, f[30], spf[30], catelea[30], loc[30][nmax+5], sploc[30][nmax+5], nrbig[nmax+5];
long long int ans=0;
string s;
int main()
{
cin>>n>>s;
for(int i=0;i<n;i++)
f[s[i]-'a']++, loc[s[i]-'a'][i]++;
spf[0]=0;
for(int i=1;i<26;i++)
spf[i]=spf[i-1]+f[i-1];
for(int i=0;i<26;i++)
{
for(int j=1;j<=n;j++)
sploc[i][j]=sploc[i][j-1]+loc[i][j];
}
for(int i=0;i<n;i++)
{
for(int j=(int)(s[i]-'a');j<26;j++)
{
nrbig[i]=nrbig[i]+(sploc[j][n]-sploc[j][i]);
}
}
for(int i=0;i<n;i++)
{
catelea[s[i]-'a']++;
/// dupa aranjarea lexi va fi pe spf[s[i]-'a']+catelea[s[i]-'a']
int pozf=spf[s[i]-'a']+catelea[s[i]-'a'];
/// inainte sa ajungem la el, unde va fi?
/// va fi mai la nrbig[i] de sfarsit
int pozi=n-nrbig[i];
ans=ans+(pozi-pozf);
}
cout<<ans;
return 0;
}