[백준] 영화수집(3653)

문제 링크 : [백준] 영화수집(3653)

문제 설명

n개의 비디오가 번호 순서대로 쌓여있습니다.(작은 수가 위로)
특정 번호의 비디오를 꺼낼 때, 그 비디오 위에 쌓여있는 비디오의 갯수를 출력합니다.
꺼낸 비디오는 제일 위에 놓습니다.

입력

T(테스트 케이스 수, 1<=T<=100)
N(비디오 갯수, 1<=N<=100,000)
M(쿼리 갯수, 1<=M<=100,000)
Q_i(M개의 쿼리, Q_i번 비디오를 꺼냅니다.)

2
3 3
3 1 1
5 3
4 4 5

출력

비디오를 꺼낼 때마다, 꺼낸 비디오 위에 몇개의 비디오가 있는지 출력합니다.

2 1 0
3 0 4

카테고리

#펜윅트리, #세그먼트트리

시간 복잡도 상한

O(QlogN)까지 가능합니다.

해결 방법

1. 아래와 같은 방법을 반복하며 풀면됩니다.
   1-1. 각 비디오의 위치를 인덱스로 하는 세그먼트 트리를 만듭니다.
   1-2. 모든 비디오는 자기 인덱스의 위치에 있기 때문에, 모든 단말노드의 값을 1로 하는 누적합 세그먼트 트리로 초기화해줍니다.
   1-3. 보고자 하는 위치보다 앞까지의 누적합을 구합니다.
   1-4. 해당 인덱스가 맨 앞으로 이동하기 때문에, 해당 위치의 값을 1에서 0으로 변경하여 누적합을 조정하여줍니다.
   1-5. 본 비디오가 맨 앞으로 이동하기 때문에, 맨 앞의 인덱스보다 하나 더 작은 인덱스의 세그먼트 트리 값을 1증가시켜줍니다.
2. 별다른 문제가 없어 보이나, 일반적인 코드 상, 최초 최소 인덱스는 1이나 1-5의 작업을 하다보면 인덱스가 음수가 나오는 경우가 발생합니다.
3. 따라서 이 문제를 해결하여 주어야합니다.
4. 인덱스를 거꾸로 하여, 1을 n으로, n을 1로 하여, 비디오를 보고 난 이후에 맨 앞 인덱스가 아니고 맨 뒤로 보내주어, Out of index 문제를 해결합니다.
5. 주의할 점은 쿼리 갯수 만큼 인덱스가 늘어나므로 처음부터 N+Q개의 인덱스를 확보해주어야합니다.
6. 설명은 세그먼트 트리로 하였으나 구현은 펜윅 트리로 하였습니다.(동작방식만 다르고 문제 풀이 컨셉은 동일합니다.)

시간복잡도

O(Qlog2N)

코드

#include<iostream>
#include<string.h>
using namespace std;
int d[200002],s,t,n,m,i,x[100001];
void update(int p,int v){
    while(p<=200001){
        d[p]+=v;
        p+=(p&-p);
    }
}
int sum(int p){
    int r=0;
    while(p){
        r+=d[p];
        p-=(p&-p);
    }
    return r;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        memset(d,0,sizeof(d));
        cin>>n>>m;
        for(i=1;i<=n;i++)update(i,1),x[n-i+1]=i;
        while(m--){
            cin>>s;
            cout<<sum(n)-sum(x[s])<<" ";
            update(x[s],-1);
            x[s]=++n;
            update(n,1);
        }
    }
}