Pagini recente » Cod sursa (job #499607) | Cod sursa (job #2834975) | Cod sursa (job #2496441) | Cod sursa (job #140819) | Cod sursa (job #658217)
Cod sursa(job #658217)
#include <fstream>
#define NMAX 500001
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f("litere.in");
ofstream g("litere.out");
struct sr {
long long v;
int p;
};
sr a[200005];
int n,i,x,val,inv,b[200005];
int Arb[NMAX];
string input;
void update(int poz,int val) {
int p,k;
while (poz<=n) {
Arb[poz]+=val;p=1;k=0;
while ((poz&p)==0) {
k++;
p<<=1;
}
poz+=(1<<k);
}
}
int query(int poz) {
int p,k,val=0;
while (poz>0) {
val+=Arb[poz];p=1;k=0;
while ((poz&p)==0) {
k++;
p<<=1;
}
poz-=(1<<k);
}
return val;
}
bool comp (sr t,sr l) {
if (t.v!=l.v) return t.v<l.v;
return t.p<l.p;
}
int main() {
memset(Arb,0,sizeof(Arb));
f >> n;f.get();
getline(f,input);
for (i=1;i<=n;i++) {
a[i].v=int(input[i-1])-int('a')+1;a[i].p=i;
}
sort(a+1,a+n+1,comp);
for (i=1;i<=n;i++) b[a[i].p]=i;
for (i=1;i<=n;i++) {
x=b[i];
inv=(inv+query(n)-query(x));
update(x,1);
}
g << inv << '\n';
f.close();g.close();
return 0;
}