#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = b; i >= a; i--)
#define cat(x) cout << #x << ": " << x << endl
using namespace std;
using ll = long long;
template<class T> struct Fenwick {
int n;
vector<T> f;
Fenwick(int n) : n(n), f(n + 1) {}
void add(int x, T v) {
for (; x <= n; x += x & -x)
f[x] += v;
}
T query(int x) {
T res = 0;
for (; x > 0; x -= x & -x)
res += f[x];
return res;
}
T sum(int a, int b) {
assert(1 <= a && b <= n);
return query(b) - query(a - 1);
}
};
const int N = 200200;
int n, match[N];
char s[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> s + 1;
n = strlen(s + 1);
vector<int> a[2];
rep(i, 1, n) a[s[i] - 'a'].push_back(i);
if (a[0].size() % 2 && a[1].size() % 2) {
cout << "-1\n";
return 0;
}
for (auto b : {a[1], a[0]}) {
for (int i = 0; i < int(b.size()); i++) {
match[b[i]] = b[int(b.size()) - 1 - i];
}
}
Fenwick<int> alive(n);
rep(i, 1, n) alive.add(i, 1);
long long res = 0;
rep(i, 1, n) {
if (match[i] == i) {
res += alive.sum(match[i] + 1, n) / 2;
}
if (match[i] > i) {
res += alive.sum(match[i] + 1, n);
}
alive.add(match[i], -1);
}
cout << res << "\n";
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <bits/stdc++.h> #define rep(i, a, b) for (int i = a; i <= b; i++) #define per(i, a, b) for (int i = b; i >= a; i--) #define cat(x) cout << #x << ": " << x << endl using namespace std; using ll = long long; template<class T> struct Fenwick { int n; vector<T> f; Fenwick(int n) : n(n), f(n + 1) {} void add(int x, T v) { for (; x <= n; x += x & -x) f[x] += v; } T query(int x) { T res = 0; for (; x > 0; x -= x & -x) res += f[x]; return res; } T sum(int a, int b) { assert(1 <= a && b <= n); return query(b) - query(a - 1); } }; const int N = 200200; int n, match[N]; char s[N]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> s + 1; n = strlen(s + 1); vector<int> a[2]; rep(i, 1, n) a[s[i] - 'a'].push_back(i); if (a[0].size() % 2 && a[1].size() % 2) { cout << "-1\n"; return 0; } for (auto b : {a[1], a[0]}) { for (int i = 0; i < int(b.size()); i++) { match[b[i]] = b[int(b.size()) - 1 - i]; } } Fenwick<int> alive(n); rep(i, 1, n) alive.add(i, 1); long long res = 0; rep(i, 1, n) { if (match[i] == i) { res += alive.sum(match[i] + 1, n) / 2; } if (match[i] > i) { res += alive.sum(match[i] + 1, n); } alive.add(match[i], -1); } cout << res << "\n"; return 0; } |
English