BOJ)3172 현주와 윤주의 재미있는 단어 게임

문제:icpc.me/3172

어떤 단어가 x가 어떤 단어 y보다 사전순으로 앞서 있으면서 y를 뒤집은 y'이 x를 뒤집은 x'보다 앞서 있다면 두 단어는 서로 좋아하지 않는다고 한다.

단어가 10만개이기 때문에 brute force로 접근한다면 시간초과를 면치 못할 것이다.

그렇기 때문에 생각을 바꾸어서 기존의 문자열 기준으로 정렬을하여 번호를 매겨준 뒤 그 번호를 가진 상태로 문자열을 다 뒤집은 후 정렬을 해주고 앞에서 부터 보면 

나보다 먼저 본 문자열 중에 나보다 할당 된 번호가 큰 문자열의 수를 세주면 된다.

이는 세그먼트 트리나 펜윅 트로로 효율적으로 해결할 수 있다.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int n, seg[400040];
long long r;
string s[100010];
pair<string, int> rs[100010];
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)return seg[node];
    if (x == y)return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)return 0;
    if (lo <= x&&y <= hi)return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    sort(s, s + n);
    for (int i = 0; i < n; i++) {
        reverse(s[i].begin(), s[i].end());
        rs[i] = { s[i],i };
    }
    sort(rs, rs + n);
    for (int i = 0; i < n; i++) {
        r += (long long)query(rs[i].second, n - 1, 1, 0, n - 1);
        update(rs[i].second, 1, 1, 0, n - 1);
    }
    cout << r;
    return 0;
}