BOJ)9463 순열 그래프

문제:icpc.me/9463

두 순열이 주어질 때 같은 번호끼리 연결할 때 생기는 교점의 수를 구하는 문제이다.

우선 첫번째 순열의 순서를 기준으로 새로운 순열 A를 생성한다.

그리고 두번째 순열의 각 번호를 순열 A에 대입한 순열 B를 생성한다.

이제 순열 B에서 현재 보고있는 i보다 오른쪽에 있고 i로 인하여 만들어지는 교점의 수는 

B[i]-1-(1~B[i]까지 이미 지나간 수들의 수)로 계산 가능하다.

1~B[i]까지 이미 지나간 수들의 수는 세그먼트 트리를 이용하여 관리할 수 있다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int t, a[100001], b[100001], x, n, seg[400004];
int update(int pos, int node, int x, int y) {
    if (y < pos || pos < x)return seg[node];
    if (x == y)return seg[node] = 1;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, node * 2, x, mid) + update(pos, 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() {
    scanf("%d", &t);
    while (t--) {
        memset(seg, 0, sizeof(seg));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            a[x] = i;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            b[i] = a[x];
        }
        long long r = 0;
        for (int i = 1; i <= n; i++) {
            r += (long long)(b[i] - 1 - query(1, b[i], 1, 1, n));
            update(b[i], 1, 1, n);
        }
        printf("%lld\n", r);
    }
    return 0;
}