Pagini recente » Cod sursa (job #2545293) | Cod sursa (job #958452) | Cod sursa (job #1611555) | Cod sursa (job #1406104) | Cod sursa (job #196926)
Cod sursa(job #196926)
#include <stdio.h>
#include <vector>
using namespace std;
int N;
vector <int> poz[30];
int aib[10010];
inline int lsb(int x) { return (x & (x - 1) ^ x); }
void update(int x)
{
while (x) {
aib[x]++;
x -= lsb(x);
}
}
int query(int x)
{
int rez = 0;
while (x <= N) {
rez += aib[x];
x += lsb(x);
}
return rez;
}
int main()
{
int i;
char c;
freopen("litere.in", "r", stdin);
freopen("litere.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++) {
scanf(" %c", &c);
poz[c - 'a'].push_back(i);
}
int pc = 0, rez = 0, q;
for (i = 0; i < 26; i++) {
for (vector <int> :: iterator it = poz[i].begin(); it != poz[i].end(); ++it) {
pc++;
q = query(*it);
rez += *it + q - pc;
update(*it);
}
}
printf("%d\n", rez);
return 0;
}