6. 3653 영화 수집

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

3653번: 영화 수집

문제 풀이 : 

#include <stdio.h>
#define MAX 200000
int tree[MAX * 3];
int pos[MAX + 1];//N장의 cd의 위치. 실제 데이터는 N+M개임. 여기서는 넉넉하게 잡음
int N, M;
void update(int node, int s, int e, int idx, int data) {
    int m;
    if (s == e) {
        tree[node] = data;
        return;
    }
    m = (s + e) / 2;
    if (idx <= m) update(node * 2, s, m, idx, data);
    else update(node * 2 + 1, m + 1, e, idx, data);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int query(int node, int s, int e, int qs, int qe) {
    int m, l, r;
    if (qs <= s && e <= qe) return tree[node];
    else if (qe < s || e < qs) return 0;//범위를 넘어서는 경우
    m = (s + e) / 2;
    l = query(node * 2, s, m, qs, qe);
    r = query(node * 2 + 1, m + 1, e, qs, qe);
    return l + r;
}
 
int main() {
    int ti, T;
    scanf("%d", &T);
    for (ti = 0; ti < T; ti++) {
        int i, no;
        for (i = 1; i < MAX * 3; i++) tree[i] = 0;//초기화
        scanf("%d %d", &N, &M);
        //1~N장 cd를 M+1 ~ N+M번째 데이터위치로 update
        for (i = 1; i <= N; i++) {
            update(1, 1, N+M, M+i, 1);  //CD가 1개 있다. //1번 cd의 실제 위치는 4번 (M+i)에 1개 갱신
            pos[i] = M + i;
        }
        //M개의 cd를 뽑아서 1~cd-1까지의 구간 합의 개수 query 구하기
        //cd를 뽑아서 위로 올리는 과정의 update
        for (i = 0; i < M; i++) {
            scanf("%d", &no);   //cd번호를 입력받는다.
            printf("%d ", query(1, 1, N+M, 1, pos[no]-1));//1~cd-1까지의 구간 합의 개수 query 구하기
            update(1, 1, N + M, pos[no], 0);    //pop도 갱신
            update(1, 1, N + M, M - i, 1);      //push도 갱신
            pos[no] = M - i;
        }
        printf("\n");
    }
 
}