[BOJ] 백준 3653 영화 수집

출처: https://www.acmicpc.net/problem/3653

 Input 

2

3 3

3 1 1

5 3

4 4 5

 

 Output 

2 1 0

3 0 4

 

처음 DVD가 놓인 위치를 M+1 ~ N까지 『1』로 표시합니다.

그리고 각 DVD의 위치를 pos[] 배열에 저장합니다.

 

Q) 4번째(= pos[4]) 놓인 DVD 위에 쌓여있는 DVD의 개수는? 

▶ 1 ~ (7-1)까지 구간의 합 = 3개입니다.

 

Q) 선택된 4번째 DVD를 어디로 옮기면 될까?

▶ 처음 M부터 해서 시작해서 1번째까지 입니다. (next = M)

    (그렇기 때문에 N 크기 앞에 M만큼 배열 크기 할당)

Q) 여기서 4번째(pos[4] = 3) DVD 위에 놓인 DVD 개수는? 구간 [1, 3-1]까지의 구간합 = 0 + 0 = 0입니다.

     if) 2번째(pos[2] = 5) DVD 위에 놓인 DVD 개수는? [1, 5-1]까지의 구간합 = 1 + 1 = 2

 

Q) 선택된 4번째 DVD 위치변화는 다음과 같습니다.

기존에 있던 자리에는 『0』 표시, 옮긴 위치에는 『1』 표시 (pos[4] = 2 값 변경)

 

Process

① i 번째 DVD의 위치 확인 → pos[i]

② 세그먼트 트리를 이용해서 [1, pos[i] - 1] 구간 합을 구합니다. 

    (i번째 영화 위에 놓여진 DVD 영화 개수)

    query([1], [2], [3], [4], [5])

        [1] = 탐색 시작 위치 (Root Node)

        [2], [3] = 탐색 범위(전체 트리 범위 = 1 ~ N+M)

        [4], [5] = 구하고자 하는 구간 범위 1 ~ pos[i]-1

        ex) pos[2]=3 >> 2번 DVD는 3번 위치에 있습니다.

        즉, query()는 i번 DVD 앞에 DVD 몇 개 있는지 확인

③ i번째 영화를 M→1순으로 해당하는 위치로 이동시킵니다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int MAX_N = 1e5;
const int MAX_M = 1e5;
const int MAX_TREE_SIZE = 1 << 19; // 4배 정도 잡아도 문제 X
int N, M;// DVD 개수, 선택 DVD 개수
int NM; // 배열개수(칸 개수, N + M)
int pos[MAX_N + 10]; // 각 영화가 놓인 실제 위치
int tree[MAX_TREE_SIZE]; // 구간합
void initTree(int n, int s, int e) { // n번 노드는 [s, e] 구간 정보를 갖고 있음
    tree[n] = 0;
    if (s == e)
        return; // 단말노드
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    initTree(L, s, m);
    initTree(R, m + 1, e);
}
int query(int idx, int start, int end, int queryLeft, int queryRight) {
    // 범위 벗어나는 경우
    if ((queryRight < start) || (end < queryLeft))
        return 0;
 
    // [s, e]가 Query 범위 포함되는 경우
    if ((queryLeft <= start) && (end <= queryRight))
        return tree[idx];
 
    int mid = (start + end) / 2;
    int L = idx * 2;
    int R = L + 1;
    return query(L, start, mid, queryLeft, queryRight) + query(R, mid + 1, end, queryLeft, queryRight);
}
void update(int n, int s, int e, int idx, int val) {
    if (s == e) { // leaf node
        tree[n] = val;
        return;
    }
 
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    if (idx > m) update(R, m + 1, e, idx, val);
    else update(L, s, m, idx, val);
    tree[n] = tree[L] + tree[R];
}
void input() {
    scanf("%d %d", &N, &M);
    NM = M + N;
    // 각 Test Case마다 초기화
    initTree(1, 1, NM);
    for (int i = 1; i <= N; i++) {
        pos[i] = M + i; // M번째부터 첫번째 DVD를 놓습니다.
        update(1, 1, NM, pos[i], 1); // DVD 존재(1), DVD 없음(0)
    }
}
void solve() {
    int target; // 선택 DVD
    int next = M; // 선택된 DVD가 옮겨지는 위치 (M~1범위, M > M-1 > M-2 ... 1)
 
    for (int i = 1; i <= M; i++) {
        scanf("%d", &target);
        // target CD 앞에 놓인 CD의 개수를 세그먼트 트리의 구간합으로 확인
        printf("%d ", query(1, 1, NM, 1, pos[target] - 1));
 
        // target CD의 위치를 next 위치에 옮기면서 트리의 값들 변경
        update(1, 1, NM, pos[target], 0); // 기존 자리에서 제거
        pos[target] = next--;
        update(1, 1, NM, pos[target], 1); // 새로운 자리에 추가
    }
    printf("\n");
}
int main() {
    int TC; scanf("%d", &TC);
    while (TC--) {
        input();
        solve();
    }
}