BOJ 9463 순열 그래프

사용한 알고리즘

세그먼트 트리

알고리즘 설명

결국 간선은 두 지점이 교차할때 생긴다.
교차 조건을 따져야 한다.
교차 조건은 두 지점 a, b에 대해서 x_a < x_b && y_a > y_b 또는 x_a > x_b && y_a < y_b인 경우이다.
위 조건에서 x좌표 앞부터 탐색하면 x_i는 j < i에 대해서 x_j < x_i 이다.
결국 앞에서 현재 y_i 보다 큰 값을 가지는 y_j 개수를 더하면 된다.
이러한 조건은 앞에서 부터 1~y_i 사이에 sum를 segTree에서 얻을 수 있다.
이후 y_i값을 segTree에 update한다.
위를 N번 반복하고 sum 값을 누적한 값이 정답이다.

풀이

// baekjoon 9463 yechan
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int SIZE = 1 << 17;
typedef pair<int,int> P;

int T, N, x, arr[SIZE*2];
int data[SIZE], data2[SIZE];

void update(int i, int val) {
    i+=SIZE;
    arr[i]=val;
    while (i > 1) {
        i /= 2;
        arr[i] = arr[i*2] + arr[i*2+1];
    }
}

int partsum(int L, int R, int nodeNum, int nodeL, int nodeR) {
    if (R < nodeL || nodeR < L) return 0;
    if (L <= nodeL && nodeR <= R) return arr[nodeNum];
    int mid = (nodeL + nodeR) / 2;
    return partsum(L, R, nodeNum*2, nodeL, mid) + partsum(L, R, nodeNum*2+1, mid+1, nodeR);
}

int main() {
    scanf("%d", &T);

    while (T--){
        scanf("%d", &N);
        memset(arr, 0, sizeof(arr));
        for (int i=1; i<=N; i++) {
            scanf("%d", &x);
            data[x] = i;
        }
        for (int i=1; i<=N; i++) {
            scanf("%d", &x);
            data2[i] = data[x];
        }

        long long cnt = 0;
        for (int i=1; i<=N; i++) {
            cnt += data2[i]-1-partsum(1, data2[i], 1, 1, SIZE-1);
            update(data2[i], 1);
        }
        printf("%lld\n", cnt);
    }
    return 0;
}