Pagini recente » Cod sursa (job #1026284) | Cod sursa (job #2505906) | Cod sursa (job #2129400) | Cod sursa (job #2307942) | Cod sursa (job #2782748)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
const int MAXN = 1e4;
int n, aib[1 + MAXN];
deque<int> dq[26];
void update(int x, int t) {
for (int i = ++x; i <= n; i += i & -i) {
aib[i] += t;
}
}
int query(int x) {
int ans = 0;
for (int i = x; i >= 1; i -= i & -i) {
ans += aib[i];
}
return ans;
}
void test_case() {
string s, t;
fin >> n >> s;
t = s;
sort(t.begin(), t.end());
for (int i = 0; i <= n - 1; ++i) {
dq[t[i] - 'a'].emplace_back(i);
}
int ans = 0;
for (int i = 0; i <= n - 1; ++i) {
int x = dq[s[i] - 'a'].front();
dq[s[i] - 'a'].pop_front();
ans += i - query(x);
update(x, 1);
}
fout << ans << '\n';
}
int main() {
int t = 1;
for (int tc = 1; tc <= t; ++tc) {
test_case();
}
return 0;
}