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;
}

Download