티스토리 뷰

알고리즘 관련/BOJ

BOJ)9463 순열 그래프

JASON 자손9319 2017. 4. 3. 21:02

문제:icpc.me/9463


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


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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&&<= 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, 0sizeof(seg));
        memset(a, 0sizeof(a));
        memset(b, 0sizeof(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], 11, n));
            update(b[i], 11, n);
        }
        printf("%lld\n", r);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2688 줄어들지 않아  (0) 2017.04.04
BOJ)2230 수 고르기  (0) 2017.04.04
BOJ)9463 순열 그래프  (1) 2017.04.03
BOJ)2992 크면서 작은 수  (0) 2017.04.03
BOJ)1058 친구  (0) 2017.04.03
BOJ)12100 2048 (Easy)  (0) 2017.03.30
댓글
댓글쓰기 폼