boj3653.cpp

#include <iostream>
#include <vector>
#include <cstdio>
 
using namespace std;
 
vector<int> tree;
vector<int> input;
vector<int> index_point;
int N, M;
 
//펜윅트리 인, 아웃 함수 정의
void in(int p, int a){
    for (; p <= N+M; p += (p&-p))
        tree[p] += a;
}
 
int out(int p){
    int sum = 0;
    for (; p; p -= (p&-p))
        sum += tree[p];
    return sum;
}
 
int main(){
    int T;
    cin >> T;
    while (T--){
        //기본 입력 세팅
        int Pre_Point;
        cin >> N >> M;
        input.resize(M + 1);
        for (int i = 1; i <= M; i++)
            scanf("%d", &input[i]);
         
        //자료 구조 사용 준비 세팅
        tree.clear(); 
        tree.resize(M+N+10);
        for (int i = 0; i <= M + N; i++)
            tree[i] = 0;
 
        for (int i = 1; i <= N; i++)
            in(M + i, 1);
 
        //dvd위치 배열 세팅
        index_point.resize(N + 1);
        for (int i = 1; i <= N; i++)
            index_point[i] = M+i;
         
        //Pre_Point는 가장 앞쪽 녀석의 위치
        Pre_Point = M+1;
        //dvd쌓기 작업 시작
        for (int i = 1; i <= M; i++){
            int now_index = index_point[input[i]];
            printf("%d ", out(now_index - 1));
            in(--Pre_Point, 1);
            in(now_index, -1);
            index_point[input[i]] = Pre_Point;
        }
        cout << endl;
    }
}