MCHAOS - Chaos Strings
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
typedef unsigned long long int64u;
#define li pair<int64u, int>
#define ll pair<int64u, int64u>
const int N = 100005;
const int lim = 10;
using namespace std;
int bit[N], p[N], n;
ll a[N];
li b[N];
int64u HASH(string s) {
int64u h = 0;
while (s.length() < lim) s = s + '`';
for(int i=0; i<s.length(); i++)
h = 27 * h + s[i] - '`';
return h;
}
void Upd(int i) {
while (i <= n) {
bit[i]++;
i += i & (-i);
}
}
int get(int i) {
int s = 0;
while (i) {
s += bit[i];
i -= i & (-i);
}
return s;
}
int main()
{
scanf("%d\n", &n);
int i, j; string s, rs;
for(i=0; i<n; i++) {
getline(cin, s); s = s.substr(0, s.length()-1);
rs = string(s.rbegin(), s.rend());
a[i] = ll(HASH(s), HASH(rs));
}
sort(a, a+n, greater<ll>());
for(i=0; i<n; i++) b[i] = li(a[i].second, i);
sort(b, b+n);
long long res = 0;
for(i=0; i<n; i++) p[b[i].second] = i + 1;
for(i=0; i<n; i++) {
res += get(p[i]);
Upd(p[i]);
}
printf("%lld", res);
return 0;
}