boj 3653: 영화 수집

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

3653번: 영화 수집

상당히 까다로운 트릭을 생각해야만 하는 문제였다.

풀이하는데 다음 링크를 참조하였다.

https://zoosso.tistory.com/398

[BOJ] 백준 3653 영화 수집

M+N개의 배열을 만들어서

(0,0,0,0.....,0) (M개) + (1,1,....1) (N개)

pos배열은 N길이로, pos[i]=value는 i번 비디오의 value = M+N 길이 배열에 자리잡은 위치를 의미한다.

가령 M=3,N=5라 가정하고, 처음 4번째를 꼭대기에 둔다고 가정해보자.

(0,0,...,0,1) (1,1,1,0,1) 이렇게 pos[4]=M으로 M 길이 배열의 끝부터 쌓는다.

그다음 3번째를 꼭대기에 둔다고 해보자.

(0,0,...0,1,1) (1,1,0,0,1) 이렇게 pos[3]=M-1로 M 길이 배열의 끝부터 차례대로 쌓는다.

그다음 4번째를 다시 꼭대기에 둔다고 해보자.

(0,0,...0,1,1,0) (1,1,0,0,1)이렇게 pos[4]=M-2로 기존 pos[4]=M이었던 M번째 위치에 있던걸 M-2번째에 위치에 둔다.

즉 한번 움직이면, update를 두번해야한다. 첫번째는 기존 pos[x]의 위치에 있던 1을 0으로 바꿔주고, 그다음엔 pos[x]의 위치를 수정 해주며, 두번째 update에서는 수정된 pos[x]위치를 0에서 1로 바꿔준다.

 

#include<bits/stdc++.h>
using namespace std;

int tc, n,m,x;

struct SegmentTree{
    int node[800081];
    int pos[100010];
    void pos_init(){
        for(int i=1;i<=n;i++) pos[i] = i+m;
    }
    int init(int start, int end, int node_idx){ // 1, n+m
        if(start==end){
            return node[node_idx] = (start > m ? 1:0);
        }
        int mid = (start+end)>>1;
        return node[node_idx] = init(start,mid,node_idx<<1) + init(mid+1,end,(node_idx<<1)+1);
    }
    int query(int start, int end, int i, int j, int node_idx){ // query(1,idx-1,1,entire)
        if(start > j || end < i) return 0;
        else if(start<=i&&j<=end) return node[node_idx];
        int mid = (i+j)>>1;
        return query(start,end,i,mid,node_idx<<1) + query(start,end,mid+1,j,(node_idx<<1) + 1);
    }
    void update(int pos_val, int i, int j, int node_idx, int diff){
        if(j<pos_val||i>pos_val) return;
        else if(j==i){ 
            node[node_idx] += diff;
            return;
        }
        int mid=(i+j)>>1;
        update(pos_val,i,mid,(node_idx<<1),diff);
        update(pos_val,mid+1,j,(node_idx<<1)+1,diff);
        node[node_idx] = node[node_idx<<1] + node[(node_idx<<1)+1];
        return;
    }
};


int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>tc;
    while(tc--){
        cin>>n>>m;
        SegmentTree ST;
        ST.pos_init();
        ST.init(1,n+m,1);
        int next=m;
        for(int i=0;i<m;i++){
            cin>>x;
            cout<<ST.query(1,ST.pos[x]-1,1,n+m,1)<<" ";
            ST.update(ST.pos[x],1,n+m,1,-1);
            ST.pos[x] = next--;
            ST.update(ST.pos[x],1,n+m,1,1);
        }
        cout<<'\n';
    }   


    return 0;
}

update는 어지간하면 void형으로 구현하는것이 나을 듯 하다. 여기서 잘못구현해서 애를 먹었다.

만약 int로 바꾼다면

 int update(int pos_val, int i, int j, int node_idx, int diff){
        if(j<pos_val||i>pos_val) return node[node_idx];
        else if(j==i){ 
            return node[node_idx] += diff;
            
        }
        int mid=(i+j)>>1;
        return node[node_idx] = update(pos_val,i,mid,(node_idx<<1),diff) + update(pos_val,mid+1,j,(node_idx<<1)+1,diff);
 }

위와같이 range를 넘어가는 순간에는 0반환이 아닌,  node를 반환해주게끔 구현해야겠다.