Pagini recente » Cod sursa (job #1955805) | Cod sursa (job #576206) | Cod sursa (job #1491067) | Cod sursa (job #2357813) | Cod sursa (job #2244461)
#include <fstream>
#include <vector>
#define CAR 135
#define VAL 10005
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
int N, i, j, X, poz;
int AIB[VAL], ANS;
vector <int> V[CAR];
string S;
int zero(int X)
{
return X & (-X);
}
void Update(int poz)
{
while (poz<=N)
{
AIB[poz]++;
poz+=zero(poz);
}
}
int Query(int poz)
{
int SUM=0;
while (poz>0)
{
SUM+=AIB[poz];
poz-=zero(poz);
}
return SUM;
}
int main()
{
fin >> N;
fin >> S;
for (i=0; i<N; i++)
V[S[i]].push_back(i+1);
for (i='a'; i<='z'; i++)
{
X=0;
while (X<V[i].size())
{
poz++;
ANS+=V[i][X]+Query(N)-Query(V[i][X])-poz;
Update(V[i][X]);
X++;
}
}
fout << ANS << '\n';
fin.close();
fout.close();
return 0;
}