BOJ 3653 영화 수집

 

문제 링크 : https://www.acmicpc.net/problem/3653

3653번: 영화 수집

 

보고 싶은 DVD 를 빼내서 가장 앞으로 가져다 놓는 작업을 한 번 하는 동안,

그 DVD 위에 있던 다른 것들은 자신 위에 쌓여 있던 개수가 모두 1 늘게 된다. 

구간에 대해 update가 필요한 상황이니 세그먼트 트리나 펜윅 트리를 쓰고 싶은 생각이 들었다.

 

다만, 빼낸 DVD 를 옮겨 놓기 때문에 약간의 트릭이 필요했다. 

쌓는다고 생각하지 말고 왼쪽부터 차례로 번호를 붙이고 본 것은 가장 왼쪽에 놓는다 해도 같은 문제일 것이다.

n+m 개의 칸이 있다고 생각하자.

처음에 m+1  번 칸에 1 번 DVD 를, m+2 번 칸에 2 번을, ... 이런 식으로 차례로 m+n 칸까지 배치할 수 있다.

그리고 이제 빼낸 것들을 차례로 m, m-1,...칸에다 옮겨놓는다고 생각할 수 있다.

 

즉 위치를 indexing 해서 구간내에 속한 것의 개수를 세는 문제로 바꾸자는 이야기.

최초 번호에 해당되는 DVD가 옮겨 다니는 위치는 arr 에 갱신함으로써 쉽게 추적할 수 있다.

 

#include<bits/stdc++.h>

using namespace std;

const int MAXN=100005;

int sz, arr[MAXN], bit[2*MAXN];

void upd(int p,int v){
    for(;p<=sz;p+=p&-p)
        bit[p]+=v;
}

int qry(int p){
    int ans=0;
    for(;p>0;p&=p-1)
        ans+=bit[p];
    return ans;
}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n,m; scanf("%d%d",&n,&m);
        sz=n+m;
        for(int i=1;i<=n;i++) {
            arr[i]=m+i;
            upd(m+i,1);
        }
        
        int head=m;
        for(int i=0;i<m;i++){
            int t; scanf("%d",&t);
            int p=arr[t];
            printf("%d ", qry(p-1));
            upd(p,-1);  
            upd(head,1);
            arr[t]=head--;
        }
        printf("\n");
        memset(bit,0,sizeof bit);
    }   
}