백준 3653:영화 수집

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

백준 3653번 영화 수집문제입니다. 세그먼트 트리를 활용해서 트리에 선택한 DVD위에 놓여있는 DVD의 갯수를 합으로 저장해 놓습니다. DVD를 뽑았다면 맨위에 두는 것을 업데이트 해가면서 문제를 풀면됩니다.

배열을 n+m(DVD갯수 + 옮길 DVD갯수)로 만들고 세그먼트트리도 같은 갯수로 만듭니다. 각 DVD의 위치를 저장해놓을 배열도 만듭니다. 각DVD의 값을 1로하는 세그먼트 트리를 만듭니다. DVD를 뽑을 때마다 세그먼트트리의 값을 갱신합니다.

참고한 블로그 (https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html)

                   (http://jaimemin.tistory.com/712)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define l(index) ((index << 1) + 1)
#define r(index) ((index << 1) + 2)
#define half(from, to) ((from + to) >> 1)
 
//세그먼트 트리를 초기화 해주는 함수
int init(vector<int>& arr, vector<int>& tree, int node, int from, int to) {
    if (from not_eq to) {
        return tree[node] = init(arr, tree, l(node), from, half(from, to))
            + init(arr, tree, r(node), half(from, to) + 1, to);
    }
    else return tree[node] = arr[from];
}
 
//해당 index의 값을 d 차이만큼 변경
void update(vector<int>& tree, int node, const int& index, int from, int to, const int& d) {
    if (index < from or index > to) return;
    tree[node] += d;
    if (from not_eq to) {
        update(tree, l(node), index, from, half(from, to), d);
        update(tree, r(node), index, half(from, to) + 1, to, d);
    }
}
 
//start ~ end 까지의 합을 구합니다.
int sum(vector<int>& tree, int node, int from, int to, const int& start, const int& end) {
    if (to < start or end < from) return 0;//구간에서 벗어나면 return 0
    else if (start <= from and to <= end) return tree[node];//구간에 포함되면 값 바로리턴
    else {//왼쪽구간과 오른쪽구간에 포함되는 구간의 값을 구해요
        return sum(tree, l(node), from, half(from, to), start, end) + 
            sum(tree, r(node), half(from, to) + 1, to, start, end);
    }
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
 
    int t; cin >> t;
    for (int test = 0; test < t; test++) {
        int n, m; cin >> n >> m;
        int h = log2(n + m) + 1;
        vector<int> arr(n + m);//배열을 m + n만큼 만들어요
        vector<int> tree((2 << h) - 1);
 
        //배열의 1~n까지는 값이 1(DVD존재) n~m까지는 0(DVD가 없음)
        for (int i = 0; i < n; i++) {
            arr[i] = 1;
        }
        init(arr, tree, 0, 0, n + m - 1);//세그먼트트리 초기화
 
        int NEW = n;//DVD를 뽑아서 놓을 새로운 위치
        vector<int> index;//해당 DVD의 위치를 저장해 놓아요
        for (int i = 0; i < n; i++) index.push_back(n - i - 1);
 
        for (int i = 0, pos; i < m; i++, NEW++) {
            cin >> pos; pos--;
 
            //맨 위부터 *내 앞*까지의 DVD갯수의 합을 출력해요
            cout << sum(tree, 0, 0, n + m - 1, index[pos] + 1, n + m - 1) << ' ';
            update(tree, 0, index[pos], 0, n + m - 1, -1);//index[pos]에서 DVD를 빼서
            index[pos] = NEW;//해당 DVD의 위치 갱신
            update(tree, 0, index[pos], 0, n + m - 1, 1);//새롭게 갱신된 DVD의 위치에 DVD를 놓아요
        }
        cout << '\n';
    }
 
    return 0;
}