MCHAOS - Chaos Strings
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 5;
char s[N][15];
long long x[N], y[N];
pair<int, int> a[N];
int n, bit[N];
void enter() {
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%s", s[i]);
}
long long hash(char * s, const bool rev = false) {
int n = strlen(s); long long res = 0;
if(rev) for(int i = n-1; i >= 0; --i) res = res * 27 + s[i] - 0x60;
else for(int i = 0; i < n; ++i) res = res * 27 + s[i] - 0x60;
for(int i = 10 - n; i > 0; --i) res *= 27;
return res;
}
void compress() {
for(int i = 0; i < n; ++i) x[i] = y[i] = hash(s[i]); sort(y, y+n);
for(int i = 0; i < n; ++i) a[i].first = lower_bound(y, y+n, x[i]) - y + 1;
for(int i = 0; i < n; ++i) x[i] = y[i] = hash(s[i], true); sort(y, y+n);
for(int i = 0; i < n; ++i) a[i].second = n - (lower_bound(y, y+n, x[i]) - y);
sort(a, a+n);
}
void increase(int v) {
for(; v <= n; v += v & -v) ++bit[v];
}
int sumTo(int v) {
int res = 0;
for(; v > 0; v -= v & -v) res += bit[v];
return res;
}
void solve() {
long long res = 0;
for(int i = 0; i < n; ++i) {
res += sumTo(a[i].second);
increase(a[i].second);
}
printf("%lld\n", res);
}
int main() {
enter();
compress();
solve();
return 0;
}