[백준 3653] 영화 수집 (C++)

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

3653번: 영화 수집

1. 주의할 점

- 값이 자주 변경 + 구간 합을 구해야 한다 → 세그먼트 트리

- TC가 여러개 → 사용하는 배열 초기화 필요

 

2. 구현

- TC가 여러개이므로 Tree[]와 Arr[] 배열을 적절히 초기화하고 시작한다

- 현재 디스크가 Num개 꽂혀있다 + M번의 이동을 수행한다 → 옮기는 디스크를 배열의 가장 뒤로 배치한다면? → 최소 N+M의 크기를 가지는 배열이 필요하다

- Tree[] 배열의 크기도 이에 따라 알맞게 설정한다

- 현재 옮기려는 디스크의 위치를 Loc[] 배열에 저장한다

- Loc[]의 값~새로 배치하려는 위치-1 사이에 존재하는 디스크의 수 = 현재 옮기는 디스크위에 쌓여 있던 디스크의 수

- 위의 조건을 만족시키기 위해, 처음 디스크 배열을 역순으로 처리한다(해당 이유는 오래동안 생각해보시면 이해갈겁니다.. 저도 2시간정도...)

- 현재 디스크가 위치해 있다면 Arr[] 배열에는 1을, 없다면 0을 저장한다

- 빨간색 조건을 구하기 위해 세그먼트 트리를 사용한다(구간합)

 

#define MAX 100001
#include <iostream>
#include <cmath>
using namespace std;
long long *tree;
int arr[2*MAX];
int loc[MAX];

long long init(int node, int start, int end){
    if(start==end) return tree[node] = arr[start];
    int mid = start + (end-start)/2;
    return tree[node] = init(node*2,start,mid)+init(node*2+1,mid+1,end);
}

void update(int node, int start, int end, int idx, int diff){
    if(start<=idx && idx<=end){
        tree[node]+=diff;
        if(start!=end){
            int mid = start + (end-start)/2;
            update(node*2,start,mid,idx,diff);
            update(node*2+1,mid+1,end,idx,diff);
        }
    }
}

long long sum(int node, int start, int end, int left, int right){
    if(left>end || right<start) return 0;
    if(left<=start && end<=right) return tree[node];
    int mid = start + (end-start)/2;
    return sum(node*2,start,mid,left,right) + sum(node*2+1,mid+1,end,left,right);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int test,num,height,see,val;
    cin>>test;
    for(int t=0;t<test;t++){
        cin>>num>>see;
        height = ceil(log2(num+see));
        tree = new long long[1<<(height+1)];
        for(int i=0;i<=num+see;i++)
            arr[i]=0;
        for(int i=1;i<=num;i++){
            arr[i]=1;
            loc[i]=num-(i-1);
        }
        init(1,1,num+see);
        for(int i=1;i<=see;i++){
            cin>>val;
            int curLoc = loc[val];
            int nextLoc = i+num;
            arr[curLoc]=0;
            arr[nextLoc]=1;
            update(1,1,num+see,curLoc,-1);
            update(1,1,num+see,nextLoc,1);
            loc[val]=nextLoc;
            cout << sum(1,1,num+see,curLoc,nextLoc-1)<<" ";
        }
        cout<<'\n';
    }
    return 0;
}